A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-05032013-125427


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
Abstract
This 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.pdf 547.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.