VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Graphenalgorithmen
Last Updated: 2026-02-05 14:57:21
Abstract
Flows in networks: algorithms of Ford-Fulkerson, Edmonds-Karp and Goldberg-Tarjan; matching problems: algorithm of Hopcroft-Karp, blossom algorithm of Edmonds; primal-dual method and its application for matching problems; planar graphs: linear testing algorithm, drawing of planar graphs; separators for trees and planar graphs and its applications; treewidth and tree decomposition.
Content
Graphen sind ein wichtiges Konzept in Informatik und Mathematik. In dieser Vorlesung werden grundlegenden algorithmische Fragestellungen diskutiert und neue Forschungsergebnisse vorgestellt. Folgender Inhalt ist geplant: - Flüsse in Netzwerken - Matchings - Travelling Salesman Problem - Planare Graphen - Separatoren und Baumweite
Resources
Literature
R. Ahuja, T. Magnanti, J. Orlin: Network Flows Prentice-Hall, 1993 W. Cook, W. Cunningham, W. Pulleyblank, A. Schrijver: Combinatorial Optimization John Wiley & Sons, 1998 T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms MIT Press, 1990 A. Gibbons: Algorithmic Graph Theory Cambridge University Press, 1985 H.J. Prömel, A. Steger The Steiner Tree Problem: A Tour Through Graphs, Algorithms and Complexity
General Information
- Language
- German
- Frequency
- Yearly recurring
Examination
- Type
- session examination
- Mode
- oral 30 minutes
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Graphenalgorithmen |
|
2 h weekly |
| exercise | Graphenalgorithmen |
|
1 h weekly |