**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)

P**lease send comments to: Ron
Shamir. email:** shamir@math.tau.ac.il