Type of Document Dissertation Author Linn, Joseph Garrett URN etd-05032013-125427 Title Path-Precedence Orders in Trees Degree PhD Department Computer Science Advisory Committee

Advisor Name Title Jeremy P. Spinrad Committee Chair Akos Ledeczi Committee Member Lawrence W. Dowdy Committee Member Paul H. Edelman Committee Member Ross M. McConnell Committee Member Keywords

- partial orders
- graph algorithms
Date of Defense 2012-11-27 Availability unrestricted AbstractThis dissertation studies classes of partial orders defined by the precedence of paths in trees, using two different notions of precedence. Strict precedence uses the same notion that interval orders use, where one path $x$ precedes another $y$ if $x$ ends before $y$ begins. Weak precedence requires only that $x$ start before and end before $y$, but the paths may intersect. Partial orders given by the weak precedence of intervals are exactly equal to the two-dimensional partial orders. Therefore, both of these notions of precedence, when applied to paths in a tree, generalize well-known and well-studied classes of partial orders.

Linear-time algorithms that construct the realizer for partial orders with a tree dia-gram are presented for both rooted and general trees. A forbidden induced-suborder characterization and new certifying recognition algorithm are given for partial orders of strict precedence in a rooted tree. The orders of weak precedence in a rooted tree are shown to have a nice intersection characterization, and such partial orders that are also bipartite can be recognized in $O(m+n)$ time. The independent set and clique problems for both of these classes are studied, and algorithms for these problems are presented which, given the tree-model as input, are asymptotically more efficient than the well-known algorithms for these problems on comparability graphs. Finally, a forbidden induced-suborder characterization of general, strict path-precedence orders is shown, leading to an $O(n^2)$ certifying recognition algorithm.

Files

Filename Size Approximate Download Time (Hours:Minutes:Seconds)

28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access linn.pdf547.49 Kb 00:02:32 00:01:18 00:01:08 00:00:34 00:00:02

Browse All Available ETDs by
( Author |
Department )

If you have more questions or technical problems, please Contact LITS.