Proseminar: Graphalgorithmen - Themen
Suche und kürzeste Wege
1. Suchverfahren I: Tiefensuche
Betreuung:
Dr. Robert Mattmüller
Bearbeitung: Sascha Oßwald
2. Suchverfahren II: A*, iteratives A*, Perimeter-Suche
Betreuung:
Dr. Robert Mattmüller
Bearbeitung: Kevin Krüssenberg
3. Kürzeste Wege I (SSP): Algorithmus von Dijkstra
Betreuung:
Dr. Julien Hué
Bearbeitung: Dominik Weis
4. Kürzeste Wege II (APSP): Algorithmus von Floyd und Warshall und Algorithmus von Johnson
Betreuung:
Dr. Julien Hué
Bearbeitung: Erik Wacker
Strukturen in Graphen
5. Zusammenhangskomponenten auf gerichteten und ungerichteten Graphen
Betreuung:
Dr. Stefan Wölfl
Bearbeitung: Adrian Batzill
6. Eulersche Kreise: Der Algorithmus von Hierholzer
Betreuung:
Dr. Stefan Wölfl
Bearbeitung: Diana Henninger
7. Kreisfreie Graphen: Topologische Sortierung
Betreuung:
Prof. Dr. Bernhard Nebel
Bearbeitung: Julien Thoma
8. Minimal spannende Bäume und Wälder: Die Algorithmen von Kruskal und von Prim
Betreuung:
Prof. Dr. Bernhard Nebel
Bearbeitung: Philipp Warth
9. Maximale Cliquen: Der Algorithmus von Bron und Kerbosch
Betreuung:
Dr. Stefan Wölfl
Bearbeitung: Maria Hügle
10. Max-Cardinality-Matchings: Der Algorithmus von Hopcroft und Karp
Betreuung:
Prof. Dr. Bernhard Nebel
Bearbeitung: Christopher Schröder
Färbungen
11. Färbung von Graphen: Greedy- und Backtracking-Algorithmen
Betreuung:
Dr. Robert Mattmüller
Bearbeitung: René Garcia Rosas
12. Färbung planarer Graphen: Algorithmus für das 5-Farben-Problem
Betreuung:
Dr. Robert Mattmüller
Bearbeitung: Tobias Paxian
13. Färbung transitiv orientierbarer Graphen
Betreuung:
Dr. Stefan Wölfl
Bearbeitung:
14. Approximative Färbungsalgorithmen: Der Algorithmus von Johnson
Betreuung:
Dr. Robert Mattmüller
Bearbeitung:
Handlungsreisen
15. Traveling-Salesman-Problem: MST-Heuristik
Betreuung:
Dr. Julien Hué
Bearbeitung: Tobias Hug
16. Traveling-Salesman-Problem: Christofides-Heuristik
Betreuung:
Dr. Robert Mattmüller
Bearbeitung:
17. Canadian-Traveler-Problem
Betreuung:
Dr. Thomas Keller
Bearbeitung: Regina König
18. Vehicle-Routing-Problem: Der Ameisenalgorithmus
Betreuung:
Dr. Stefan Wölfl
Bearbeitung: Jens Hoffmann
Flüsse und Ströme
19. Maximale Flüsse: Der Algorithmus von Edmonds und Clark
Betreuung:
Prof. Dr. Bernhard Nebel
Bearbeitung:
20. Maximale Flüsse: der Algorithmus von Dinic
Betreuung:
Prof. Dr. Bernhard Nebel
Bearbeitung: Philipp Bausch
21. Maximale Flüsse: der Push-Relabel-Algorithmus
Betreuung:
Dr. Stefan Wölfl
Bearbeitung:
22. Kosten-minimale Flüsse: der Algorithmus von Klein
Betreuung:
Dr. Stefan Wölfl
Bearbeitung:
23. Kosten-minimale Schnitte: der Algorithmus von Stoer und Wagner
Betreuung:
Dr. Julien Hué
Bearbeitung: