Literatur |
• T.H. Cormen, C.E. Leiserson, R. Rivest, C. Stein, Algorithmen-Eine Einführung, Oldenbourg 2004, ISBN 3-486-27515-1. • A. Brandstädt, Graphen und Algorithmen, Teubner Verlag 1994, ISBN 3-519-02131-5. • K. Mehlhorn, Graph Algorithms and NP-Completeness, Springer, 1984, ISBN 3-540-13641-x. Ergänzende Empfehlungen: • S. Even, Graph Algorithms, Computer Science Press 1979, ISBN 0- 914894-21-8. • M. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics 57, Elsevier 2004, 2nd edition, ISBN 0-444- 51530-5. |
Lerninhalte |
Das Modul führt in die Grundlagen effizienter Graphenalgorithmen für Informatiker ein, behandelt grundlegende Probleme undMethoden wie vollständiges Durchsuchen von Graphen, kürzesteWege in Graphen, minimum spanning trees, Maximalfluß in Netzwerken, das Matchingproblem, Färbungsprobleme sowie Baumstrukturen in Graphen und Dekomposition sowie Weitebegriffe. Außerdem werden einige spezielle Klassen behandelt wie z.B. chordale Graphen, Intervallgraphen, perfekte Graphen sowie planare Graphen. Inhalte • Graphen und ihre Darstellung • Tiefensuche (DFS) und Breitensuche (BFS) sowie Varianten • Mimimalgerüste (minimum spanning tree) und greedy-Algorithmus • die Algorithmen von Kruskal, Dijkstra und Sollin • das Steinerbaumproblem und Varianten • Maximalfluß in Netzwerken und Anwendungen • Algorithmus von Dinitz; Komplexität • das maximum matching Problem und Varianten • Knoten- und Kantenf¨arbungen in Graphen mit Anwendungsbeispielen • chordale Graphen und Intervallgraphen; perfekte Graphen • Baumstruktur in Graphen, modulare Dekomposition, treewidth, cliquewidth • planare Graphen, graph drawing und Anwendungen sowie Komplexitätsfragen |