Uni-Logo

This page is only available in German.

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: