Dept. of Computer Science 

School of Mathematical Sciences

Tel Aviv University

February 1997

Advanced Topics in Graph Algorithms

Instructor: Prof. Ron Shamir.

Administration

Lectures: Sundays 16:00-19:00, Physics 114.
Office hours: Thursdays 16:00-17:00, Schreiber 115.
Grader: Dekel Tsur
Course Homepage: http://www.math.tau.ac.il/~shamir/atga97.html

Each student will be assigned as a scribe (i.e., to prepare lecture notes) for one lecture. The notes should be prepared in Latex within a week following the lecture, then corrected by Dekeland me, and finally revised by the student and distributed in class. All this process must be complete within two weeks from the original lecture. Notes should contain all the material presented in class, written in clear and accurate fashion. Use figures and diagrams to clarify things. Use the scribes from former years with caution, as some material has changed and some errors stilll persist in them.

There will be no final exam. Exercize sets will be given every other week or so and will serve as a take home exam. Solutions should be done INDEPENDENTLY by each student and without help from others. Use of books and articles for the solutions is allowed and will not affect the grading, but the sources should be noted in the solutions. Final grade: 70% exercize sets + 30% scribe work.

Look here for all Course Material (current and old stuff)

Tentative Course Outline

Basic graph concepts, intersection graphs, interval graphs sneak preview. Basic algorithmic concepts and data structures, BFS, DFS, Transitive tournaments and topological sorting. Examples of some real life applications of special graph classes.

Perfect Graphs: The perfect graphs theorem.

Chordal graphs: Fulkerson-Gross, Dirac Thms. perfect elimination order algorithms. Chordal graphs as intersection graphs. Chordal graphs and evolutionary trees. The Minimum Fill In Problem. Optimization algorithms on chordal graphs.

Comparability Graphs: implication classes and Gamma-chains. Uniquely Partially Orderable graphs G-decomposition and characterizations characterization of cocomparability graphs as function graphs. Characterization Theorem. polynomial recognition algorithm. Some optimization algorithms. partial order dimension.

Interval Graphs: Gilmore-Hoffman Theorem.Lekkerkerekr-Boland Theorem. Interval graph models in temporal reasoning. constrained interval graphs and interval sandwich problems. recognition of matrices with consecutive and circular ones. PQ trees. Physical mapping problem. Pathwidth and interval graphs. Preference and Indifference: semiorder, Roberts' theorem, unit and proper interval graphs.

Other Graph Families: split graphs ; threshold graphs ; Circular arc Graphs ; permutation graphs ; perfect elimination bipartite graphs. chordal bipartite graphs. Greedily solvable network flow problems. ;ATF graphs.

Scheinerman' characterization of intersection graphs.

Actual course outline for the current semester gradually appears here.

Bibliography

main reference: M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs . Academic Press, New York, 1980.

C. Berge. Graphs and Hypergraphs . North-Holland, Amsterdam, 1973.

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, 1979.

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)