Algorithms and characterizations of special graphs in the chordal hierarchy

Research in algorithmic graph theory and its applications has increased considerably in recent years. It is due to that graph theory serves as a mathematical model for any system involving a binary relation, and that there are applications to many areas. The design of algorithms on graphs is generally restricted to graphs having special structures. Since their introduction by Claude Berge in the early 1960s (5), perfect graphs have attracted considerable attention. One of the first class of graphs to be recognized as being perfect is the class of chordal graphs. The class of chordal graphs is a well understood graph class which is algorithmically useful and exhibits several interesting characterizations. It arises in many application areas. The main theme of this dissertation is to investigate graphs which are in the chordal graph hierarchy, and to develop efficient sequential and parallel algorithms for these graphs. In this dissertation, we investigate characterizations and properties of doubly chordal graphs, and we present sequential and parallel algorithms for the recognition of doubly chordal graphs. Next, we present results on the maximum k-colorable subgraph problem for doubly chordal and strongly chordal graphs. Finally, we show results on the maximum k-dependent set problem for chordal, doubly chordal, interval and proper interval graphs.