Advanced Topics in Graph Algorithms

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.

• 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

  ---

  (Sept. 2021) To read the lectures in Ukranian - https://mobilemall.pk/atga.html

  ---

  (Oct. 2016) To read the lectures in Indonesian - http://www.chameleonjohn.com/translations/atga-Indonesian

  ---

  (Dec. 2016) To read the lectures in Bulgarian - http://carrrsmag.com/blog/grafika-algoritmi.html

  ---

  (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

  ---

  (September 2018) To read the lectures in Greek - https://www.voonky.com/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.