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)