Hauptseminar (Bachelor): Advanced Graph Algorithms
General Information
Course instructors: Andreas S. Schulz and Alexander Grosz
Dijkstra, Kruskal and Ford-Fulkerson are examples of well-established algorithms on graphs and networks - but there's much more to discover!
In this seminar we will discuss a broad range of other problems and algorithms on graphs.
Schedule
- Session 1 (E), Monday 2024-01-22 14:00.
- Session 2 (C, B), Wednesday 2024-01-24 14:00.
- Session 3 (A, D, F), Wednesday 2024-01-24 16:30.
Topics
- A: Steiner Trees
The contraction lemma enables the construction of approximation algorithms for the Steiner tree problem due to Berman & Ramayer and Zelikovsky). [1, Chapter Approximation Algorithms for the Steiner Tree Problem in Graphs, Sections 1-2] - B: Graph Coloring
The five colour theorem and Brooks' theorem give central results by constructive proofs in the colourability of graphs. [2, Chapter 5] - C: Edmond's Blossom Algorithm
This algorithm is an efficient method of computing a maximal matching in a general graph. [3, Chapter 13] - D: The Push-Relabel Algorithm
This algorithm due to Goldberg & Tarjan has been an important step in the development of more efficient maximum flow computations. [3, Chapter 6] - E: Minimum-Cost Flows
Algorithms by Klein and Busacker & Gowen. [3, Chapter 10] - F: Routing Games and the Price of Anarchy
The problem of routing a flow through a network is also a relevant question in game theory. This topic discusses the discrepancy between optimal solutions and equilibrium states of the game. [4, Chapter 18] - G: NP-Hardness in Restricted Graphs
The concept of NP-hardness is discussed on a chain of reductions. At the end of this chain, the problem of deciding the 3-colourability of a planar graph with degree at most 4 is shown to be as hard to solve as any other problem in NP. [5]