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
- Problem Set 1 (Discussion: Nov 21, 2017) (solution sketch)
- Problem Set 2 (Discussion: Nov 28, 2017) (solution sketch)
- Problem Set 3 (Discussion: Dec 4&5, 2017) (solution sketch)
- Problem Set 4 (Discussion: Dec 11&12, 2017) (solution sketch)
- Problem Set 5 (Discussion: Dec 18&19, 2017) (solution sketch)
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.