General Information

Course instructors: Andreas S. Schulz, Lukas Brandl, Alexander Grosz

The presentations will take place in seminar room 2906.DG.009 (local room number 6009). This room is not in Garching. Some helpful advice for your presentation can be found here.

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 as outlined in the topics below.

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] [9, Chapter 20.1]
• B: Graph Coloring
  The five colour theorem and Brooks' theorem give central results by constructive proofs in the colourability of graphs. [2, Chapter 5] [9, Chapter 16.3]
• C: Computing Maximum Flows
  The Edmonds-Karp algorithm and Capacity Scaling algorithm extend the basic approach by Ford-Fulkerson to provide efficient maximum flow computations. [3, Chapter 6] [10, Chapter 7.3]
• D: Minimum-Cost Flows
  Algorithms by Klein/Goldberg & Tarjan and Busacker & Gowen. [3, Chapter 10] [9, Chapter 9]
• E: 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] [5, Selfish Routing and Proportional Resource Allocation]
• F: A Simple Min-Cut Algorithm
  Stoer and Wagner present an algorithm to compute a minimum cut that is not based on flow computations (as compared to most previous results), but on an iterative construction of the graph instead. This approach has been generalized to the class of symmetric submodular functions by Queyranne. [6] [7] [9, Chapters 8.7, 14.5]
• G: Randomized Min-Cut Computation
  Yet another approach for solving the problem of finding a minimum cut in a graph due to Karger. This efficient randomized algorithm finds an/all optimal solutions with high probability. [8] [9, Exercise 8.39]

Literature

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. Gems of Combinatorial Optimization and Graph Algorithms DOI
6. Stoer & Wagner, A simple min-cut algorithm, 1997 DOI
7. Queyranne, Minimizing symmetric submodular functions, 1998 DOI
8. Karger & Stein, A new approach to the minimum cut problem, 1996 DOI
9. Korte & Vygen, Combinatorial Optimization, 2018 DOI
10. Ahuja, Magnanti & Orlin, Network flows theory, algorithms, and applications

Recommended Reading:

In [9], read the following sections:

• Chapter 7.1 (Shortest Paths/Dijkstra)
• Chapter 8.1-2 (Max-Flow-Min-Cut Theorem/Ford-Fulkerson, Menger's Theorem)
• Chapter 9.1-2 (Minimum Cost Flows)