Graph Algorithms ppt pdf

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