TUM – TUM – Menü

Advanced Graph Algorithms
lecture

Graphs are a fundamental concept in discrete mathematics. Optimization problems in graphs appear in a large variety of application areas. This course covers algorithms for graph problems such as for Shortest Paths, Network Flows, and Matchings. It will focus on advanced algorithms that go beyond those discussed in the courses Algorithmic Discrete Mathematics or Combinatorial Optimization. It will also cover more involved graph-based models such as Disjoint Paths Problems, Flows over Time, and Stable Matchings.

Lecturer: Jannik Matuschke
Teaching assistant: Marinus Gottschau
Weekly hours: 2+1 (4+2 over 6 weeks)
ECTS credits: 5

News Schedule Lecture notes Problem sets Literature

News

  • Q&A session on January 8 at 16:00 in 03.08.011.
  • Solution sketches online.
  • Registration for exams: You can register for the exam until Dec 31 in TUMonline.
  • Reminder: You can evaluate the course until Dec 17.
  • Problem Set 5 online.
  • Problem Set 4 online.
  • The lecture on Dec 4 starts at 16:15 (this is a one time change only).
  • Updated schedule: Tutorial A moved to Mon 17:45 in Room 03.08.011.
  • Problem Set 3 online.
  • Problem Set 2 online.
  • Problem Set 1 online.

Schedule

The course will be going on over 6 weeks from November 13 to December 19.
The first lecture is on Nov 13. The first tutorial classes are on Nov 21.
Exams will take place in the third week of January (approximately).

Lectures

Day Time Room Lecturer
Mon 16:00-17:30 03.08.011 Jannik Matuschke
Tue 12:15-13:45 03.08.011 Jannik Matuschke

Tutorial Classes

Group Day Time Room Lecturer
A Mon 17:45-19:15 03.08.011 Marinus Gottschau
B Tue 16:15-17:45 03.08.011 Marinus Gottschau

Lecture notes/slides

  • Lecture 1 (Nov 13, 2017): Introduction to the Course, Spanning Trees and Arborescences. Suggested Reading: Sections 6.1 & 6.2 from Korte & Vygen's book. (slides) (notes)
  • Lecture 2 (Nov 14, 2017): Shortest Path Problems. Suggested Reading: Sections 7.1 & 7.2 from Korte & Vygen's book. (slides) (notes)
  • Lecture 3 (Nov 20, 2017): Network Flows: Max Flow/Min Cut. Suggested Reading: Chapter 8 of Korte & Vygen's book. (slides) (notes)
  • Lecture 4 (Nov 21, 2017): Network Flows: Augmenting Path Algorithm, Capacity Scaling. Suggested Reading: Chapter 8 of Korte & Vygen's book. (slides)
  • Lecture 5 (Nov 27, 2017): Network Flows: Preflow/Push Algorithm. Suggested Reading: Chapter 8 of Korte & Vygen's book. (slides)
  • Lecture 6 (Nov 28, 2017): Network Flows: Minimum Mean Cycle Canceling Algorithm. Suggested Reading: Sections 9.1-9.3 of Korte & Vygen's book. (slides) (notes)
  • Lecture 7 (Dec 4, 2017): Multicommodity Flows and Disjoint Paths. Suggested Reading: Chapter 19 of Korte & Vygen's book, the article by Fortune, Hopcroft and Wyllie . (slides) (notes)
  • Lecture 8 (Dec 5, 2017): Disjoint Paths (continued), Bipartite Matchings. Suggested Reading: Sections 10.1 & 10.3 of Korte & Vygen's book. (slides) (notes, updated)
  • Lecture 9 (Dec 11, 2017): Matchings: Hall's Theorem, Tutte's Theorem. Suggested Reading: Sections 10.1 & 10.3 of Korte & Vygen's book. (slides) (notes)
  • Lecture 10 (Dec 12, 2017): Matchings: Edmonds' Matching Algorithm. Suggested Reading: Section 10.5 of Korte & Vygen's book. (slides) (notes)
  • Lecture 11 (Dec 18, 2017): Matchings: Edmonds' Matching Algorithm (continued), Gallai-Edmonds Decomposition. Section 10.5 of Korte & Vygen's book. (slides) (notes)
  • Lecture 12 (Dec 19, 2017): Minimum Weight Perfect Matchings, Stable Matchings. Suggested Reading: Sections 11.2-11.3 of Korte & Vygen's book; Section 1.1 of Kleinberg & Tardos' book. (slides) (notes)

Outlook

  • Q&A Session (January 8, 2017)

Problem sets

Literature

  • B. Korte, J. Vygen. "Combinatorial Optimization: Theory and Algorithms". Springer Verlag, 5th edition, 2012.
  • R. Ahuja, T. Magnanti, J. Orlin. "Network flows: Theory, Algorithms, and Applications". Prentice Hall, 1993.
  • A. Schrijver. "Combinatorial Optimization: Polyhedra and Efficiency". Springer Verlag, 2003.
  • S. Fortune, J. Hopcroft, J. Wyllie. "The Directed Subgraph Homeomorphism Problem" . Theoretical Computer Science 10:111-121, 1980.
  • J. Kleinberg, É. Tardos. "Algorithm Design". Pearson, 2005.

Research Unit M9


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

Professors

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

News

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