Advanced Topics in Graph Algorithms


This archive contains material on the course "Advanced Topics in Graph Algorithms" © taught by Ron Shamir in the department of Computer Science of Tel-Aviv university, on 10/91-2/92 (Fall 92), 4-6/94 (Spring 94) and 4-6/97 (Spring 97). This was a one-semester graduate course open also to seniors, with one three-hour meeting each week.

The course emphasized algorithmic and structural aspects of "nice" graph families, in particular perfect graphs, interval graphs, chordal graphs and comparability graphs.
In Fall 92 the course was based to a large extent on the classic book of Martin C. Golumbic "Algorithmic Graph Theory and Perfect Graphs' (Academic Press, 1980), and in some parts also on the manuscript "The Art of Combinatorics", by Douglas B. West.
The Spring 94 and Spring 97 course had a similar basis, but emphasized more recent material, and made a lot of reference to applications in molecular biology. (See the webpage Algorithms for Molecular Biology for much more on these aspects.)
For translations to multiple languages see below.


Material available: