Course: Advanced Topics in Graph Algorithms Spring 1994
-------------------------------------------------------
Introduction
Apr 21 1 *basic graph concepts
*intersection graphs
*interval graphs sneak preview (Gloumbic Ch. 1)
*examples of applications of special graph families
Perfect graphs
Apr 28 2 *The Perfect Graph Theorem (Golumbic Ch 3.2)
May 5 3 *p-critical graphs
*polytope characterizations of perfect graphs
*the strong perfect graph conjecture
(Golumbic Ch 3.-)
Trigangulated Graphs:
*Fulkerson-Gross, Dirac Thms.
(Golumbic Ch. 4.1-3)
*perfect elim. order algorithm: MCS complexity
(Tarjan-Yannakakis)
May 12 4 *MCS validity
(Tarjan-Yannakakis)
*Alg to verify a given elim order is perfect
(Golumbic Ch. 4.)
*Triangulated graphs as intersection graphs
(Golumbic Ch. 4.5)
May 19 5 *Minimum Fill In is NP-complete
(Yannakakis)
*Triangulated graphs are perfect
(Golumbic Ch. 4.6)
May 26 6 *Algs for computing chromatic and stability
numbers on triangulated graphs
(Golumbic Ch. 4.7)
Comparability Graphs:
* implication classes and Gamma-chains
(Golumbic Ch. 5.1)
June 02 7 * Uniquely Partially Orderable graphs
(Golumbic Ch. 5.2)
* G-decomposition and characterization theorems
(West; Golumbic Ch. 5.4)
* recognition algorithm via bipartite graphs
June 05 8 Guest lecture: Marty Golumbic
Cocomparability graphs:
* permutations graphs are the comparability and
cocomparability graphs.
* cocomparability graphs are f-graphs.
Tolerance graphs:
* constant tolerance graphs are interval graphs
* tolerance graphs with tolerance=interval length
are permutation graphs.
* bounded tolerance graphs are cocomparability
grpahs
* tolerance graphs are perfect.
Comparability Graphs:
June 09 9 * Recognition algorithm and complexity
* perfectness and Dilworth theorem.
* Algorithm for max weighted clique
* Algorithm for max independent set
* partial order dimension
(Golumbic Ch. 5.4-7)
June 16 10 * comparability invariants
* series-parallel posets and cographs
(Mohring's survey)
Interval Graphs:
* Gilmore-Hoffman Characterization
* Fulkerson-Gross Characterization
(Golumbic Ch. 8.2)
* Lekkerkerekr-Boland Characterization Thm (no proof)
(Fishburn CH. 3.4)
* Preference and Indifference: semiorder,
(Golumbic Ch. 8.3,5)
June 23 11 * Unit interval graph characterizations
(Golumbic Ch. 8.3,5, others)
* Interval graph recognition algorithm
(Ramalingam-Rangan 1990)
* consecutive and circular ones recognition,
PQ trees (no proofs)
(Golumbic Ch. 6)
* extensions of interval graphs:
maximum submatrix with C1P
minimizing the total number of 1-blocks
consecutive sets
(Kou '77)
June 30 12
Temporal Reasoning:
* Allen's model, ISAT, MLP, ACSP.
* Interval sandwich is NP-complete.
* polynomial algorithm for A3-<>.
(Golumibc-Shamir 90)
Physical mapping and graph width:
* completion problems
* pathwidth and interval graphs
* proper pathwidth and unit interval graphs
* proper pathwidth = bandwidth
* algorithm for inerval sandwich graph with bounded
clique size.
* parameterized intractability of the problem
(Kaplan-Shamir 93)
* parameterized tractability of the chordal
completion problem
(Kaplan-Shamir-Tarjan 93)
------not given -------------------------------------------------
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)