Algorithms on special classes of graphs and partially ordered sets
Tze-Heng Ma, Jeremy Spinrad · 1990
This thesis addresses a variety of problems on special classes of graphs and partially ordered sets. Special classes of graphs arise in many applications. On these classes of graphs, many problems are found to have faster algorithms. We first present a fast algorithm for split decomposition. Split decomposition has been used in solving other problems. Recently, it provides the basis for recognition algorithms on circle graphs. Substitution decomposition is a more restricted version of split decomposition. We introduce a linear time algorithm to perform substitution decomposition on chordal graphs. Some potential applications are also pointed out. Matrix multiplication is a commonly used tool in solving many combinatorial problems. For example, it provides the fastest algorithm to solve the transitive closure and the neighborhood containment problems. We show that by using a characterization of N-free posets, we can avoid matrix multiplication and find a faster algorithm for the transitive closure problem on N-free posets. The chain subgraph cover problem has been a useful vehicle in proving NP-completeness of many open problems. In this thesis, we further explore the relationship between chain graphs and posets. We also find many problems which can be easily transformed into the two chain subgraph cover problem. By presenting an O($n\sp2$) reduction from the two chain subgraph cover problem to the partial order dimension two problem, we develop O($n\sp2$) algorithms for bidimension two, Ferrers dimension two, interval dimension two, and trapezoid graph recognition problems. The dimension of posets is one of the most studied invariant of posets. A poset is called cycle-free if its comparability graph is chordal. Using the clique tree representations of chordal graphs, we prove that every cycle-free poset is at most 4 dimensional.