Atlas home || Conferences | Abstracts | about Atlas
Host: Fields Institute
Sponsor: The Connaught Committee, University of Toronto and the Faculty of Arts and Science, University of Toronto.
Homepage: http://www.fields.utoronto.ca/gt-families.html
Email: families@fields.utoronto.ca
Organizers: Derek Corneil (University of Toronto), Jerry Spinrad (Vanderbilt University), Lorna Stewart (University of Alberta)
Description:
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).
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)
Date received: September 30, 1999
© 2008 Atlas Conferences Inc.