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 NPcomplete 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, cocomparability and weakly chordal);
"near perfect" graphs (e.g. asteroidal triplefree, partial ktrees,
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.