|July 29, 2014|
Special Year on Graph Theory and Combinatorial Optimization Program
Workshop on Structured Families of Graphs
Monday, May 8 to Saturday, May 13, 2000
Derek Corneil University of Toronto
The development of many graph algorithms is motivated by applications in such diverse areas as computational biology, electrical and industrial engineering, and the social sciences. Although the associated graph problems are often NP-complete for arbitrary graphs, sometimes efficient algorithms are possible when the problem is restricted to classes of graphs that provide a good model of the actual applications. Furthermore, for problems in P, simpler, more efficient algorithms are often possible for these restricted graph classes. In order to produce such algorithms, it is necessary to understand and then exploit the structure of the restricted graph class. Often the study of the structure of the graph family leads to fundamental theoretical questions; the Strong Perfect Graph Conjecture is a prime example of this.
The aim of this workshop is to highlight recent theoretical and algorithmic advances for these restricted graph classes. Examples of such classes include: perfect graphs and the various subclasses (e.g. chordal, interval, comparability, co-comparability and weakly chordal); "near perfect" graphs (e.g. asteroidal triple-free, partial k-trees, and circular arc); topological graphs (e.g. planar, outerplanar and toroidal).
Financial support has been received from The Connaught
Committee, University of Toronto