-
Tue 18.10.2011: Introduction: motivation and basic graph theory definitions. The (corrected) slides are here.
-
Thu 20.10.2011: Introduction, continued:
basic graph theory definitions, continued (slides).
Basics of algorithm analysis (slides).
-
Tue 25.10.2011: Basics of algorithm analysis, continued: Lists, graph representations and deleting degree 1 vertices in linear time.
The slides are here, with some remarks added.
-
Thu 27.10.2011: Basics of algorithm analysis, continued: constructing the different graph representations in linear time, and DFS trees. The slides are here.
-
Tue 1.11.2011: Connectivity: basic definitions and blocks. The (corrected) slides are here. An alternative proof of Proposition 4.5 has been added.
-
Thu 3.11.2011: Connectivity: more about blocks, and a linear time algorithm for finding the blocks of a graph. The (corrected) slides are here.
-
Tue 8.11.2011: Connectivity: Menger's Theorem and corollaries.
The slides can be found here.
-
Thu 10.11.2011: Connectivity: Maximum flows and minimum cuts.
The slides can be found here.
-
Tue 15.11.2011:
Maximum flows and minimum cuts, continued. The slides can be found here.
Matchings: basic definitions and matchings in bipartite graphs. The (corrected) slides can be found here.
-
Thu 17.11.2011:
Matchings in general graphs: Tutte's Theorem on perfect matchings, and why it is hard to find augmenting paths in non-bipartite graphs. The slides can be found here.
-
Tue 22.11.2011:
Matchings in general graphs: Edmonds' algorithm for finding a maximum (unweighted) matching in general graphs. The slides can be found here.
-
Thu 24.11.2011:
Matchings in general graphs: A certifying extension of Edmonds' algorithm. The Tutte-Berge formula: a tight upper bound for the size of a maximum matching. The slides can be found here (the new slides start at slide 18).
-
Tue 29.11.2011:
Weighted matchings:
Minimum weight perfect matchings in bipartite graphs: an algorithm and a tight lower bound.
Minimum weight perfect matchings in general graphs: a tight lower bound. The slides are here
-
Thu 1.12.2011:
Weighted matchings, continued: Edmonds' algorithm for finding a minimum weight perfect matching; blossom contraction and expansion. (Slides)
Edge colorings: Definitions and basic bounds. (Slides)
-
Tue 6.12.2011:
Edge colorings, continued: Vizing's Theorem, and an algorithm for finding good edge colorings. (Slides, until slide 16).
-
Thu 8.12.2011:
An application of edge colorings: constructing time tables.
Approximation algorithms for finding edge colorings and other graph problems (vertex cover, maximum acyclic subgraph). (Slides, starting at slide 17).
-
Tue 13.12.2011:
Vertex coloring: introduction and basic bounds.
The slides are here (up to slide 15).
-
Thu 15.12.2011:
Vertex coloring continued:
(Approximation) algorithms for Vertex Coloring in various graph classes.
Chromatic polynomials.
The slides are here (starting at slide 16).
-
Tue 3.1.2012:
Vertex coloring continued:
Chordal graphs and perfect elimination orders.
Perfect graphs: introduction.
The (corrected) slides of the first part (chordal graphs) are here. Some proofs have been added to the slides.
-
Thu 5.1.2012:
Vertex Coloring continued:
Perfect graphs: examples of perfect graph classes, and the weak and strong perfect graph theorem.
Coloring: summary of the previous lectures. The slides are here.
Tree decompositions:
Series parallel graphs, introduction. The slides are here (Lemma 8.2 and its proof have been added).
-
Tue 10.1.2012:
Tree decompositions, continued:
Recognizing series parallel graphs in linear time and space.
The definition of tree decompositions.
The slides are here (starting at slide 12).
-
Thu 12.1.2012:
Tree decompositions, continued:
Basic properties of tree decompositions.
The slides are here. (Updated 17.1.2012.)
-
Tue 17.1.2012:
Tree decompositions, continued:
Dynamic programming over tree decompositions: algorithms for 3-Colorability and Independent Set.
The slides are here.
-
Thu 19.1.2012:
Dynamic programming over tree decompositions, continued:
Constructing nice tree decompositions, and a linear time and space complexity bound for the dynamic programs.
The slides are here (new slides start at 14).
-
Tue 24.1.2012:
3-connected components: definitions and properties.
The slides are here.
-
Thu 26.1.2012:
3-connected components:
SPR decompositions: decompositions into 3-connected components.
The slides are here (starting at slide 16).
-
Tue 31.1.2012:
Planar graphs:
Introduction. Embeddings, Euler's formula, subdivisions of K_5 and K_{3,3}.
The slides are here (slides 1-15).
-
Thu 2.2.2012:
Planar graphs, continued:
A polynomial time certifying algorithm for planarity testing.
Straight line embeddings, triangulations and maximal planar graphs.
Embeddings: equivalence, rotation systems and combinatorial embeddings.
The corrected slides are here (slides 16-31).
-
Tue 7.2.2012:
Embeddings, continued:
Encoding plane graphs, Whitney's Theorem on embeddings of 3-connected graphs, Mac Lane's Theorem on the number of embeddings of a graph, Kuratowski's Theorem, and SPQR trees. The slides are here (slides 31-45).
-
Thu 9.2.2012:
Planar graphs: Layer decompositions and approximation schemes.
Dual graphs. A diameter/tree width bound for planar graphs. Layer decompositions. A PTAS for Maximum Independent Set on planar graphs.
The slides are here.
-
Tue 14.2.2012:
Layer decompositions, continued: a PTAS for Minimum Dominating Set on planar graphs.
A polynomial time algorithm for Max-Cut in planar graphs.
The slides are here (starting at slide 66).
-
Thu 16.2.2012:
Summary and exam preparation. Slides.
Last modified: Thu February 16, 2012
