TUM – TUM – Menü

Network Flows (MA5518)

Network flows are a central concept in combinatorial optimization, with many important applications in areas such as transportation, communication, or production. This course covers advanced network flow topics that extend upon the basic max flow and min cost flow problems:
  • multicommodity flows
  • flows over time
  • robust flows
  • generalized flows
  • flow computation in planar graphs

Lecturer: Jannik Matuschke
weekly hours: 2+1 hours
ECTS credits: 5

News Schedule Lecture notes Problem sets Literature


  • The course is over, thank you for participating!



Day Time Room Lecturer
Tue 16:00-17:30 00.07.014 Jannik Matuschke

Tutorial Classes

Day Time Room Lecturer
Thu (biweekly) 10:15-11:45 03.08.011 Jannik Matuschke

Lecture notes/slides

  • Lecture 1 (April 19, 2016): maximum flow problem, max flow/min cut, augmenting path algorithm, flow decomposition, capacity scaling. Suggested reading: Sec. 8.1 of Korte-Vygen; Lecture 5 of David Williamson's course
  • Lecture 2 (April 26, 2016): push/relabel algorithm. Suggested reading: Sec. 8.5 of Korte-Vygen
  • Lecture 3 (May 3, 2016): minimum cost flow problem, minimum mean cycle canceling algorithm. Suggested reading: Sec 9.1-9.3 of Korte-Vygen
  • Lecture 4 (May 10, 2016): running time of minimum mean cycle canceling algorithm. Suggested reading: Sec 9.3 of Korte-Vygen
  • Lecture 5 (May 24, 2016): successive shortest path algorithm, multicommodity flows. Suggested reading: Sec 9.4 and 19.1 of Korte-Vygen
  • Lecture 6 (May 31, 2016): FPTAS for maximum multicommodity flow. Suggested reading: Sec 19.2 of Korte-Vygen
  • Lecture 7 (June 2, 2016): cut and distance criterion for multicommodity flows, arc-disjoint paths problem, flows over time. Suggested reading: Sec 19.1 of Korte-Vygen, Sec 1-2 of Skutella's Introduction to Network Flows Over Time.
  • Lecture 8 (June 14, 2016): algorithm for the maximum flow over time problem, max flow/min cut over time, earliest arrival flows. Sec 1-3 of Skutella's Introduction to Network Flows Over Time.
  • Lecture 9 (June 16, 2016): earliest arrival flow algorithm, minimum cost flows over time. Sec 3-4 of Skutella's Introduction to Network Flows Over Time; if you want to see earliest arrival flows in action, try out the ZET Evacuation Tool .
  • Lecture 10 (June 21, 2016): time-expanded networks, multicommodity flows over time. Suggested reading: Sec 4-5 of Skutella's Introduction to Network Flows Over Time and the article  by Groß and Skutella on speed-up through storage for multi-commodity flows.
  • Lecture 11 (June 28, 2016): robust flows. Suggested reading: Lecture notes on robust flows.
  • Lecture 12 (July 12, 2016): maximum flows in planar graphs. Suggested reading: Borradaile & Klein's article , Sections 2.3 & 4 of Lattices and maximum flows in planar graphs .

Problem sets


Research Unit M9

Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
phone:+49 89 289-16858
fax:+49 089 289-16859


Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics


April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.