Advanced Topics in Graph Algorithms
This archive contains material on the course
"Advanced Topics in Graph Algorithms" © taught by
Ron Shamir
in the department
of Computer Science of
TelAviv university,
on 10/912/92 (Fall 92), 46/94 (Spring 94) and 46/97 (Spring 97).
This was a onesemester graduate course open also to seniors,
with one threehour meeting each week.
The course emphasized algorithmic and structural aspects of "nice"
graph families, in particular perfect graphs, interval graphs, chordal
graphs and comparability graphs.
In Fall 92 the course was based to a large extent on the classic
book of
Martin C. Golumbic "Algorithmic Graph Theory and Perfect
Graphs' (Academic Press, 1980),
and in some parts also on the manuscript
"The Art of Combinatorics", by
Douglas B. West.
The Spring 94 and Spring 97 course had a similar basis, but
emphasized more recent material, and made
a lot of reference to applications in molecular biology.
(See the webpage
Algorithms for Molecular Biology
for much more on these aspects.)
Material available:
 Detailed course outline .
 Spring 1997 course material
(unorganized; some links were not updated and some
material is readable only to TAU browsers. Sorry.)

Scribes of Spring 94 lectures
Talks were scribed by the students and revised by the lecturer.
The complete set of notes was subsequently edited and formatted
by
Sariel HarPeled .
Thanks, Sariel !
You can either download the
complete notes as a single postscript file (150 pages), Or each
lecture seperately.
 Cover page
 Table of Content
 List of Figures
Lecture #1:
Introduction to Graph Theory
 Basic Definitions and Notations
 Intersection Graphs
 Circulararc Graphs
 Interval Graphs
 Line graphs of bipartite graphs
 Definition of perfect graph
 Some Definitions and Properties
 Perfect Graph Theorem
Lecture #3:
Perfect and Triangulated Graphs
 Perfect Graphs
 $p$Critical Graphs
 A Polyhedral Characterization of Perfect Graphs
 The Strong Perfect Graph Conjecture
 Triangulated Graphs
 Introduction
 Characterizing Triangulated Graphs
 Recognizing Triangulated Graphs
 Time Complexity
Lecture #4:
Recognizing Triangulated Graphs
 Recognizing Triangulated Graphs
 Generating a PEO
 Testing an Elimination Scheme
 Naive Algorithm
 Efficient Algorithm
 Example
 Correctness of the Algorithm
 Complexity of the Algorithm
 Triangulated Graphs as Intersection Graphs
 Evolutionary Trees
 Triangulated Graphs as Intersection Graphs
Lecture #5:
Triangulated Graphs Are Perfect
 Triangulated Graphs Are Perfect
 Proving This Property
 Other Results
 Computing the Minimum Fill In
 The Problem
 Fill In is NPHard
 Chain Graphs
 Optimal Linear Arrangement (OLA)
 Chain Graph Completion (CGC)
 The result for Fill in
 Problems
Lecture #6:
Algorithms for triangulated graphs and comparability graphs
 Some Optimization Algorithms on Triangulated Graphs
 Computing the chromatic number and all maximal cliques
 Finding $\alpha $ and $k$
 Comparability Graphs
 Some Definitions
 Implication Classes
 The Triangle Lemma
 Decomposition of Graphs
Lecture #7:
Uniquely Partially Orderable Graphs
 Uniquely Partially Orderable Graphs
 Characterizations and Recognition Algorithms
Lecture #8:
Some interesting graph families characterized by intersection
 Introduction
 Permutation graphs
 $F$Graphs
 ``The air controllers strike''
 A composition of permutation diagram.
 Tolerance graphs
 Interval graphs as a subset of tolerance graphs.
 Bounded and unbounded tolerance graphs.
 Comparability Graph Recognition
 The Complexity of Comparability Graph Recognition
 Implementation
 Complexity Analysis
 Coloring and Other Problems on Comparability Graphs
 Comparability Graphs Are Perfect
 Maximum Weighted Clique
 Calculating $\alpha (G)$
 The Dimension of Partial Orders
Lecture #10:
Comparability invariants and Interval Graphs
 Comparability invariants
 Interval graphs
 Preference and Indifference
 Recognizing interval graphs
 A quadratic algorithm 1
 A Linear Algorithm
 More about the consecutive 1's property
 Temporal Reasoning and Interval algebras
 Interval satisfiability problems
 Interval sandwich problems and ISAT
 A linear time algorithm for ISAT($\Delta _1}$)
 Bandwidth, Pathwidth and Proper Pathwidth
Please send all feedback and comments to:
shamir@math.tau.ac.il
(Nov. 2011) To read the lectures in Ukranian  http://webhostinggeeks.com/science/graphalgorithmsua
(Oct. 2016) To read the lectures in Indonesian  http://www.chameleonjohn.com/translations/atgaIndonesian
Back to Ron's home page
© TelAviv University.
Last update: July 11, 1996