THEMATIC PROGRAMS
December 22, 2024

Special Year on Graph Theory and Combinatorial Optimization Program

Workshop on Structured Families of Graphs

Monday, May 8 to Saturday, May 13, 2000

Schedule

Organizing Committee:

Derek Corneil University of Toronto
Jerry Spinrad Vanderbilt University
Lorna Stewart University of Alberta

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).

 

Invited Speakers:

  • Andreas Brandstadt,University of Rostock

  • Martin Golumbic, Bar Ilan University

  • Michel Habib, Universite de Montpellier

  • Wen Lian Hsu, Academia Sinica

  • Frederic Maffray, Université de Grenoble

  • Uri Peled, University of Illinois at Chicago

  • Ron Shamir, University of Tel Aviv

  • Jerry Spinrad, Vanderbilt University

  • Lorna Stewart, University of Alberta

  • Doug West University of Illinois, Urbana

Financial support has been received from The Connaught Committee, University of Toronto
and the Faculty of Arts and Science, University of Toronto.