Many interesting problems in graph theory are NP-complete on general graphs. In practical applications, however, one rarely has to contend with general graphs: quite often sufficient structure is available to limit the graphs under investigation to a restricted class. A class of graphs with a wide spectrum of applications (in communications, transportation, VLSI design, program optimization, database design, and other areas of computer science, and engineering) that has engaged the interest of researchers is the class of perfect graphs. The scope of the current research in this area now extends to the mathematical and algorithmic properties of particular classes of perfect graph, their generalizations, and graph parameters motivated by them. The purpose of this project is to apply the powerful tool of graph decomposition to a large class of perfect graphs, for the purpose of revealing its algorithmic properties both in the form of efficient algorithms and lower bound results. Results that impact computing practice are expected: this work is seeking simpler and faster algorithms featuring a robust behavior in the sense that they should perform well even on "near-misses": graphs outside the class under investigation.
