AG Kombinatorische Optimierung
Graphenalgorithmen
Modul ALG-9-G (9 LP),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
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.