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 Tel-Aviv university, on 10/91-2/92 (Fall 92), 4-6/94 (Spring 94) and 4-6/97 (Spring 97). This was a one-semester graduate course open also to seniors, with one three-hour 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.)
For translations to multiple languages see below.

Material available:

Detailed course outline .
- Spring 97 (HTML)
- Spring 94 (ASCII)
- Fall 92 (ASCII)

Spring 1997 course material (unorganized; some links were not updated and some material is readable only to TAU browsers. Sorry.)
- course official webpage
- course active webpage

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 Har-Peled . Thanks, Sariel !
You can either download the complete notes as a single postscript file (150 pages), Or each lecture seperately.
For translations of the lecture notes to other languages see here.
Cover
- Cover page
- Table of Content
- List of Figures
Lecture #1: Introduction to Graph Theory
- Basic Definitions and Notations
- Intersection Graphs
- Circular-arc Graphs
- Interval Graphs
- Line graphs of bipartite graphs
Lecture #2: Perfect 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 NP-Hard
    - 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.
Lecture #9: Comparability 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
Lecture #11: Interval Graphs
- Preference and Indifference
- Recognizing interval graphs
  - A quadratic algorithm 1
  - A Linear Algorithm
- More about the consecutive 1's property
Lecture #12: Temporal Reasoning
- 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
Index

Please send all feedback and comments to: rshamir@tau.ac.il
Translations

(Nov. 2011) To read the lectures in Ukranian - http://webhostinggeeks.com/science/graph-algorithms-ua
(Oct. 2016) To read the lectures in Indonesian - http://www.chameleonjohn.com/translations/atga-Indonesian
(Nov. 2016) To read the lectures in Russian - http://www.enginearena.com/blog/graph-algorithms/:
(Dec. 2016) To read the lectures in Estonian - http://www.autoteileprofi.de/science/2016/12/01/tapsemalt-teemasid-graafik-algoritmid
(Dec. 2016) To read the lectures in Bulgarian - http://carrrsmag.com/blog/grafika-algoritmi.html
(June 2017) To read the lectures in French - https://bestreviewsbase.com/translations/#advanced-topics-in-graph-algorithms:FR
(June 2017) To read the lectures in Czech - https://www.zoobio.se/teaching/2017/06/22/pokrocila-temata-v-grafove-algoritmy/
(October 2017) To read the lectures in Swedish - https://www.espertoautoricambi.it/science/2017/10/02/avancerade-aemnen-i-grafen-algoritmer/
(February 2018) To read the lectures in Spanish - http://clipart-library.com/atga.html
(May 2018) To read the lectures in German - https://essayhilfe.de/wissenschaft/#Advanced-Topics-in-Graph-Algorithms:DE
(June 2018) To read the lectures in Dutch - http://www.ncsm.nl/wetenschap#Advanced-Topics-in-Graph-Algorithms:NL
(September 2018) To read the lectures in Punjabi - https://www.bydiscountcodes.co.uk/translations/advanced-topics-in-graph-algorithms/
(September 2018) To read the lectures in Greek - https://www.voonky.com/advanced-topics-in-graph-algorithms/
(January 2019) To read the lectures in Armenian - https://thcdetox.biz/education/advanced-topics-in-graph-algorithms/
(July 2019) To read the lectures in Chinese - https://mattressmozz.com/portfolio/advanced-topics-in-graph-algorithms
(October 2020) To read the lectures in Catalan - https://www.ibidemgroup.com/edu/traduccion-catalan-algoritmos/
Back to Ron's home page

© Tel-Aviv University.

Advanced Topics in Graph Algorithms

Cover

Lecture #1: Introduction to Graph Theory

Lecture #2: Perfect Graphs

Lecture #3: Perfect and Triangulated Graphs

Lecture #4: Recognizing Triangulated Graphs

Lecture #5: Triangulated Graphs Are Perfect

Lecture #6: Algorithms for triangulated graphs and comparability graphs

Lecture #7: Uniquely Partially Orderable Graphs

Lecture #8: Some interesting graph families characterized by intersection

Lecture #9: Comparability Graphs

Lecture #10: Comparability invariants and Interval Graphs

Lecture #11: Interval Graphs

Lecture #12: Temporal Reasoning

Index

Translations