Algorithmen auf Graphen


Seminar im Grundstudium NWI - SoSe 2004

Veranstalter:	Jens Reeder (jreeder(at)techfak...)  M3-114
Belegnummer:	392017
Zeit:	Donnerstag 16 ct - 18
Ort:	C01 - 136
Scheinkriterien:	30-45 minütiger Vortrag und schriftliche Ausarbeitung
	(ungefähr 6 Seiten)
Voraussetzung:	Algorithmen und Datenstrukturen I

Graphen und Algorithmen auf Graphen sind in vielen Teildisziplinen der Informatik von Bedeutung. Viele Probleme kann man als Graphenprobleme formulieren, wie z.B. Fragestellungen im Bereich der Stoffwechselweganalyse, Routenplanung, Programmcodeanalyse usw.. Auch das Internet ist ein riesiger Graph und wir können es nur aufgrund effizienter Graphalgorithmen nutzen.

In diesem Seminar sollen einerseits grundlegende Graphalgorithmen kennen-gelernt und andererseits das Vortragen in wissenschaftlichem Rahmen geübt werden. Im Anschluss an jeden Vortrag findet daher auch eine kurze Diskussion über den Vortragstil statt.

Themenliste

1. Graphrepräsentationen, Breadth-first und Depth-first Search (Kap. 23: S. 465-484 in [CLR90]); Random Graph Generators (S. 46-54 in [Sed04])
2. Simple, Eulerian and Hamilton Paths (Kap. 17.7: S. 57-68 in [Sed04])
3. Topological sort, strongly connected components (Kap. 23: S. 485-493 in [CLR90])
4. Minimum Spanning Trees (Kap. 24 in [CLR90] und Kap. 20 in [Sed04])
   • Kruskal's Algorithm
   • Prim's Algorithm
5. Single Source Shortest Path (Kap. 25 in [CLR90])
   • Dijkstra
   • Bellmann-Ford
   • SSSP in DAG's
6. All-Pairs Shortest Paths (Kap. 26: 550-563 in [CLR90])
7. Flow Networks, Maximum Flow, Ford-Fulkerson Algorithm (Kap. 27: S. 579-600 in [CLR90]
8. Heuristiken zum Traveling Salesman Problem (S.969-973 in [CLR90] and [RSL77])
9. PageRank: Der Algorithmus hinter Google [LSMW98]

Vortragsplan

Datum	Vortragender	Thema
29.4	-	Vorbesprechung
6.5	J.R.	Grundlegende Begriffe und Algorithmen (1)
13.5	Sascha McSporran	Simple, Eulerian and Hamilton Paths (2)
27.5	-	-
3.6	Christoph Hermes	Single Source Shortest Path (5)
24.6	Benjamin Gess	All-Pairs Shortest Paths (6)
1.7	Martin Krzykawski	Flow Networks  (7)
8.7	-	Google (9)