CS 762 Graph-Theoretic Algorithms



Objectives

To give the student further exposure to the design, analysis, and application of algorithms for problems defined on graphs.

Students are expected to have basic knowledge of algorithm design and analysis.

References

To be determined.

Schedule

Three hours of lecture per week.

Outline

Planar Graphs (12 hrs)

Linear-time planarity testing and embedding algorithms. Decomposing planar graphs. Series-parallel, outerplanar, k-outerplanar graphs; recognition and fast algorithms for problems defined on these classes.

Trees and Tree-like Graphs (12 hrs)

Techniques for solving NP-complete problems on trees. Generalizations to graphs of bounded pathwidth and treewidth. Implications of the Robertson-Seymour graph minors project.

Perfect Graphs and Intersection Graphs (12 hrs)

Recognition and fast algorithms for problems defined on chordal graphs, comparability graphs, permutation graphs, cographs, interval graphs, circular arc graphs, and claw-free graphs.


Campaign Waterloo

David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293
Fax: 519-885-1208

Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics


Valid HTML 4.01!Valid CSS! Last modified: Friday, 01-Jun-2012 11:00:32 EDT


Menu:ShowHide