The PR-tree data structure is introduced to characterize the sets of path-tree models
of path graphs. We further characterize the sets of directed path-tree models of directed
path graphs with a slightly restricted form of the PR-tree called the Strong PR-tree.
Additionally, via PR-trees and Strong PR-trees, we characterize path graphs and directed path graphs by their Split Decompositions. Two distinct approaches (Split Decomposition and Reduction) are presented to construct a PR-tree that captures the path-tree models of a given graph G = (V, E) with n = |V| and m = |E|. An implementation of the split decomposition approach is presented which runs in O(nm) time. Similarly, an implementation of the reduction approach is presented which runs in O(A(n + m)nm) time (where A(s) is the inverse of Ackermann’s function arising from Union-Find [40]). Also, from a PR-tree, an algorithm to construct a corresponding Strong PR-tree is given which runs in O(n + m) time. The sizes of the PR-trees and Strong PR-trees produced by these approaches are O(n + m) with respect to the given graph. Furthermore, we demonstrate that an implicit form of the PR-tree and Strong PR-tree can be represented
in O(n) space.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/32678 |
| Date | 20 August 2012 |
| Creators | Chaplick, Steven |
| Contributors | Corneil, Derek |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0019 seconds