Vorlesung Graphenalgorithmen

Viele Anwendungsprobleme aus der Praxis können als Graphenprobleme formuliert werden. In dieser Vorlesung beschäftigen wir uns mit einer Auswahl unterschiedlicher Graphenprobleme und betrachten verschiedene Strategien diese zu lösen. Gerade das Erlernen dieser verschiedenen möglichen Herangehensweisen bildet den Kern dieser Vorlesung. Wir werden Probleme betrachten für die sich effiziente (d.h. polynomielle) Algorithmen finden lassen, und algorithmische Techniken kennenlernen um die erforderliche Laufzeit zu drücken. Ebenso werden wir uns aber auch mit NP-schweren Problemen beschäftigen: Auch für diese Aufgaben hat das Feld der Algorithmik einiges zu bieten! Wir werden Algorithmen diskutieren, die solche Probleme z.B. beweisbar effizient lösen können, wenn bestimmte Instanzeigenschaften erfüllt sind - als Beispiel sei die Klasse der Graphen mit fixer Baumweite genannt (was immer dieses Konzept genau bedeutet; wir werden es in der Vorlesung schon noch definieren). Auf der anderen Seite werden wir auch FPT-Algorithmen kennen lernen, also Algorithmen die die Lösung exakt polynomiell berechnen können, unter der Voraussetzung, dass die Zielfunktion beschränkt werden kann. Schliesslich werden wir auch Ansätze diskutieren, wie man NP-schwere Graphenprobleme (ohne bestimmte Parameter, wie oben genannt, zu kennen) oft in der Praxis dennoch exakt lösen kann, wenn man es nur geschickt angeht. Da ich die Auswahl der Probleme gerne auch ein bisschen abhängig vom Vorwissen der Teilnehmer machen möchte, seien die folgenden Probleme nur exemplarisch aufgelistet, um eine Ahnung zu erhalten: Färbe-, Matching- und Schnittprobleme; Tour-, Netzwerkdesign- und Augmentierungsprobleme; Planarität, etc. Technische Universität Dortmund WiSe 2013/14 Lehrstuhl Informatik XI Univ.-Prof. Dr. Mutzel Petra