AG Kombinatorische Optimierung
Graphenalgorithmen
(V4+Ü2)
Inhalt
Graphen gehören zu den wichtigsten Modellen der Informatik die
zahlreiche praktische Anwendungen haben (z.B. im Verkehrs- und
Telekommunikationsbereich, der Produktionsplanung oder allgemein bei
vielen kombinatorischen Optimierungsproblemen).
Nach einer Einführung in die Grundbegriffe der Graphentheorie werden Suchverfahren, Zusammenhangs-Probleme, Bäume, Kürzeste Wege, Matching- und Routing-Probleme, Knoten- und Kantenfärbungen sowie Netzflussprobleme behandelt. Dabei steht die Entwicklung von effizienten Lösungsverfahren im Vordergrund. In den Übungen sollen einige Algorithmen auch praktisch implementiert werden.
Literatur
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin: Network Flows, Prentice Hall, 1993
- J.M. Aldous, R.J. Wilson: Graphs and applications, Springer, 2003
- R. Diestel: Graphentheorie, Springer, 2000
- J. Gross, J. Yellen: Graph theory and its applications, CRC Press, 1999
- J. Gross, J. Yellen: Handbook of graph theory, CRC Press, 2004
- D. Jungnickel: Graphen, Netzwerke und Algorithmen, BI-Verlag, 1987
- R. Sedgewick: Algorithms, Addison Wesley, 1988
- V. Turau: Algorithmische Graphentheorie, Oldenbourg, 2004
- Internet-Ressourcen zu Graphenalgorithmen
Materialien
Teilnahme
Die Veranstaltung ist vorgesehen für B.Sc. ab dem 2. Semester. Teilnehmen können alle interessierten Studierenden aus den Studiengängen Informatik, Mathematik, Angewandte Systemwissenschaft und Cognitive Science.