## 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]