Dept. of Computer Science
School of Mathematical Sciences
Tel Aviv University
Advanced Topics in Graph Algorithms
Instructor: Prof. Ron Shamir.
Actual Course Outline: Spring
Lecture 1, February 16th: Introduction: Basic
graph concepts, intersection graphs, interval
graphs sneak preview. Examples of some real life applications of special
Lecture 2, February 23: Perfect
Graphs: Lovasz perfect graphs theorem. p-critical graphs. The strong
perfect graph conjecture.
Lecture 3, March 2nd: Chordal
graphs: Fulkerson-Gross, Dirac Thms. Tarjan-Yannakakis MCS algorithm
for generating a perfect elimination order. Linear algorithm to test if
a vertex order is a PEO. Chordal graphs as intersection graphs.
Lecture 4, March 9th: Chordal
graphs and evolutionary trees. The Minimum Fill In Problem. Relation to
sparse matrix factorization. Yannakakis proof that Minimum Fill In is NP-complete.
Lecture 5, March 16th: Chordal
graphs are perfect. Computing the chromatic number and all maximal cliques
in a chordal graph. Computing the stability number and a clique partition.
Parameterized analysis of the Minimum Fill In Problem: Two algorithms
showing the problem is fixed parameter tractable (Kaplan, Shamir, Tarjan)
Lecture 6, March 30th: Comparability
Graphs: implication classes and Gamma-chains. Uniquely Partially
Orderable graphs, Shevrin-Filipov theorem. G-decomposition and characterizations.
Lecture 7, April 6th: Comparability
graph characterization Theorem. Two polynomial recognition algorithms.
Some optimization algorithms. Partial order dimension. Dushnik-Miller Theorem.
Lecture 8, April 13th:Comparability
Graphs: Gilmore-Hoffman Theorem.Lekkerkerekr-Boland Theorem (w/o
proof) . Preference and Indifference: semiorder, Roberts' theorem, unit
and proper interval graphs.
Lecture 9, May 4th:
Interval graph recognition: Ramalingan-Pandu Rangan algorithm;
The consecutive ones problem (C1P) and Physical mapping of DNA;
Booth-Leuker PQ-trees linear algorithm for C1P and interval graph
Extensions of C1P; interval number; circular ones property.
Lecture 10, May 18th
(guest speaker: Martin
Circle graphs and overlap graphs; Function graphs;
Golumbic-Rotem-Urrtia characterization theorem.
Strong Matchings; Polynomiality on cocomparability graphs
Trapezoid Graphs: Dagan-Golumbic-Pinter characterization theorem;
Lecture 11, May 25th
Interval graph applications:
Interval graph models in temporal reasoning,
constrained interval graphs and interval sandwich problems (Golumbic
Shamir 93). Other sandwich problems.
Treewidth, pathwidth, bandwidth, and their connections to
interval and unit interval graphs (Kaplan Shamir 96)
Lecture 12, June 1st:
Every graph is an intersection graph; Intersection classes.
Injective interscetions classes.
Scheinerman's characterization for intersection classes of graphs;
Line graphs: properties and characterizations.
Material Planned but Not covered this time:
Graph Families: split graphs ; threshold graphs ; Circular
arc Graphs ; perfect elimination bipartite graphs.
chordal bipartite graphs. Greedily solvable network flow problems. ATF
main reference: M. C. Golumbic. Algorithmic Graph
Theory and Perfect Graphs . Academic Press, New York, 1980.
C. Berge. Graphs and Hypergraphs . North-Holland,
S. Even. Graph Algorithms. Computer Science Press,
Rockville, Maryland, 1979.
P. Fishburn. Interval Orders and Interval Graphs.
Wiley, New York, 1985.
M. R. Garey and D. S. Johnson. Computers and Intractability:
A Guide to the Theory of NP-Completeness. W. H. Freeman and co., San Francisco,
G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial
Optimization . Wiley, New York, 1988.
Ch. Papadimitriou and K. Steiglitz. Combinatorial
Optimization: Algorithms and Complexity . Prentice-Hall, Englewood
Cliffs, New Jersey, 1982.
F. S. Roberts. Discrete Mathematical Models, with
Applications to Social Biological and Environmental Problems. Prentice-Hall,
Englewood Cliffs, New Jersey, 1976.
D. B. West. The Art oc Combinatorics: Volume
I: Extermal Graph Theory. (manuscript, Fall 1996)
Please send comments to: Ron
Shamir. email: firstname.lastname@example.org