Dept. of Computer Science
School of Mathematical Sciences
Tel Aviv University
Advanced Topics in Graph Algorithms
Instructor: Prof. Ron Shamir.
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.
here for all Course Material (current
and old stuff)
Tentative Course Outline
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
Graphs: The perfect graphs theorem.
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: 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
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
Graph Families: split graphs ; threshold graphs ; Circular
arc Graphs ; permutation graphs ; perfect elimination bipartite graphs.
chordal bipartite graphs. Greedily solvable network flow problems. ;ATF
characterization of intersection graphs.
Actual course outline for the current semester gradually appears here.
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