Course: Advanced Topics in Graph Algorithms Fall 1991/2
-------------------------------------------------------
Oct 16 1 basic graph concepts
intersection graphs
interval graphs sneak preview (Gloumbic Ch. 1)
Oct 23 2 basic algorithmic concepts and ata structures
BFS, DFS
Transitive tournaments and topological sorting
(Golumbic Ch. 2)
Oct 30 3 The Perfect Graph Theorem (Golumbic Ch 3.2)
Nov 6 4 Trigangulated Graphs:
*Fulkerson-Gross, Dirac Thms.
*perfect elim. order algorithm: Lex BFS validity
(Golumbic Ch. 4.1-3)
Nov 13 5 Trigangulated Graphs:
*Lex BFS complexity
*Alg to verify a given elim order is perfect
*Triangulated graphs as intersection graphs
(Walter-Gavril theorem except 1=>3)
(Golumbic Ch. 4.3-5)
Nov 20 6 Trigangulated Graphs:
*Triangulated graphs as intersection graphs
(Walter-Gavril theorem 1=>3)
(Golumbic Ch. 4.5)
*Minimum Fill In is NP-complete
(Yannakakis)
*Triangulated graphs are perfect
(Golumbic Ch. 4.6)
Nov 27 7 Trigangulated Graphs:
*Algs for comuting chromatic and stability
numbers on triangulated graphs
(Golumbic Ch. 4.7)
Comparability Graphs:
* implication classes and Gamma-chains
(Golumbic Ch. 5.1)
Dec 04 8 Comparability Graphs:
* Uniquely Partially Orderable graphs
(Golumbic Ch. 5.2)
* G-decomposition and characterizations
(first part of Golumbic Ch. 5.4)
Dec 11 9 Guest lecture: Marty
Dec 18 10 Comparability Graphs:
* Characterization Theorem
* Recognition algorithm and complexity
* perfectness and Dilworth theorem.
* Algorithm for max weighted clique
* partial order dimension
(Golumbic Ch. 5.4-7)
Dec 25 11 Interval Graphs:
* Gilmore-Hoffman Characterization Thm
(Golumbic Ch. 8.2)
* Lekkerkerekr-Boland Characterization Thm
(Fishburn CH. 3.4)
Jan 1 12 Temporal Reasoning:
* Allen's model, ISAT, MLP, ACSP.
* Interval sandwich is NP-complete.
* polynomial algorithm for A3-<>.
(Golumibc-Shamir 90)
Jan 8 13 Interval Graphs:
* consecutive and circular ones
recognition, PQ trees (no proofs)
* Preference and Indifference: semiorder,
Roberts' theorem
(Golumbic Ch. 8.3,5)
* split graphs (survey)
(Golumbic Ch. 6)
Jan 16 14 brief reviews:
* Circular arc Graphs
(Golumbic Ch. 8.6)
* permutation graphs
(Golumbic Ch. 7)
* perfect elimination bipartite graphs
* chordal bipartite graphs.
(Golumbic Ch. 11)
* Greedily solvable network flow problems
(Adler-Hoffman-Shamir 90)