Graphs and Algorithms (2WO08)

The course will be taught in 2010-2011 by Cor Hurkens, Rudi Pendavingh and Judith Keijsper. We will use the lectures notes previously use by Bert Gerards, which are available at GA lecture notes by Bert Gerards.
Location and time depend on weekday:

Tentative programme

Part 1: Prerequisites, and Planar graphs

Lecturer: Rudi Pendavingh, rudi@win.tue.nl, room HG 9.30.

The section numbers below refer to the lecture notes of Bert Gerards.

Lecture 1 (Wed, 02-02-2011)

Graphs, sets, numbers. Sections 1.1 and 1.2.

Lecture 2 (Thu, 03-02-2011)

Binary spaces, algorithms. Sections 1.3 and 1.4.

Lecture 3 (Wed, 09-02-2011)

Plane graphs, Euler's formula. Section 3.1.

Lecture 4 (Wed, 16-02-2011)

Colouring maps. Section 3.2.

Lecture 5 (Thu, 17-02-2011)

Kuratowski's Theorem. Section 3.3.

Lecture 6 (Wed, 23-02-2011)

Plane duality. Section 3.4.

Lecture 7 (Wed, 02-03-2011)

Kruskal's theorem on quasi-ordered trees (handouts)

Part 2: Matchings

Lecturer: Cor Hurkens, wscor@win.tue.nl, room HG 9.29.

The section numbers below refer to the lecture notes of Bert Gerards.

Lecture 1 (Wed, 16-03-2011)

Matchings, Section 2.1: Solving bipartite matching by hand.

Lecture 2 (Thu, 17-03-2011)

Max Cardinality Matchings, Section 2.2a: augmenting paths/walks, solving bipartite case.

Lecture 3 (Wed, 23-03-2011)

Max Cardinality Matchings, Section 2.2b: shrinking blossoms, solving non-bipartite case.

Lecture 4 (Thu, 24-03-2011)

Edmonds-Gallai structure, Section 2.2c.

Lecture 5 (Wed, 30-03-2011)

Hopcroft-Karp for fast bipartite matching , Section 2.2d.

Lecture 6 (Thu, 31-03-2011)

Min Weight Perfect Matchings, Section 2.3.

Lecture 7 (Thu, 21-04-2011)

Matching Duality, Section 2.4.

Lecture 8 (Fri, 29-04-2011)

Parity Constraints, Section 2.5.

Lecture 9(?) (Wed, 04-05-2011)

spare (Friday roster!)

Part 3: Paths and Flows

Lecturer: Judith Keijsper, jkeijspe@win.tue.nl, room HG 9.31.

The section numbers below refer to the lecture notes of Bert Gerards.

Lecture 1 (Thu, 12-05-2011)

Relating the different variants of disjoint paths problems. Cut conditions. Path packing algorithmically. Sections: 1.1 (Menger, MaxFlowMinCut), 1.4, 1.5 (Graph Search), 4.0, and 4.3, including all relevant exercises (In Exercise 4.8, derive the directed internally vertex disjoint case from the directed arc disjoint case!).

Lecture 2 (Fri, 13-05-2011)

Disjoint paths in acyclic directed graphs. Section 4.1.
Fractional multicommodity flows. A necessary and sufficient condition for a feasible multiflow to exist has been formulated. Material: Section 9.1 of Schrijver's lecture notes `A course in combinatorial Optimization'
Exercises: see Section 9.1 and 9.3 of Schrijver's lecture notes.

Lecture 3 (Thu, 19-05-2011)

When is the cut-condition sufficient for existence of a feasible multiflow? Hu's Theorem on fractional/half-integral 2-commodity flows. Rothschild and Whinston's Theorem on integral 2-commodity flows. Section 9.2. of Schrijver's lecture notes (see Lecture 2). Exercises: see Section 9.2 of Schrijver's lecture notes.

Lecture 4 (Fri, 20-05-2011)

Material: section 4.4 Gerards.

Lecture 5 (Thu, 26-05-2011)

Material: section 9.5 Schrijver.
Exercises: see section 9.5 Schrijver.

Lecture 6 (Fri, 27-05-2011)

Continuation of Schrijver. Discussion of exercises.

Lecture 7 (Thu, 16-07-2011)

Material: section 4.2 Gerards. Questions on all exercises.

Lecture 8 (Fri, 17-07-2011)

spare