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.


  • 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.


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


  • [1] Steiner Trees in Industry (eds. Cheng, Du), 2001 DOI
  • [2] Diestel, Graph Theory, 2017 DOI
  • [3] Jungnickel, Graphs, Networks and Algorithms, 2013 DOI
  • [4] Algorithmic Game Theory (eds. Nisan et al.), 2007 DOI
  • [5] Garey et al., Some simplified NP-complete graph problems, 1974 DOI