[Back]

E. Paisios:
"Generic Programing for Graph Problems Using Tree Decompositions";
Supervisor: N. Musliu, F. Wei; Institut für Informationssysteme, Arbeitsbereich Datenbanken & Artificial Intelligence, 2008.

Tree decompositions have heen an increasingly useful tool for solving problems on graphs due to the important algorithmic properties of the dass of graphs of bounded treewidth. An important theorem by Courcelle [Con9O] stated that properties definable in MSO logic can be decided in linear time on graphs of bonnded treewidth. T`his provided a theoretical base which revealed tractability of rnany graph problems, intractable in the general case, for the aforementioned dass of graphs and instigated many algorithms solving MSO-definable problems. Bodlaender proposed a dynamic programming approach to designing algorithms using tree decompositions [Bod9Y]. Tue approach encompassed several of the algorithrns already invented, hut was also used as a method for the construetion of new ones for a variety of graph problems.
In this thesis we studied and iniplemented this approach, delivering a systein that operates using plug-ins to describe the speeific parts of algorithms using Bodlaender`s method. Furthermore we implemented a 3 colouring algorithm as a plug-in for the system in order to assess its usability and efficicncy.
General Terms ftee decompositions, Dynainic programming.
Keywords Graph theory, dynamic programming, parameterized complexity, trec decomposition, bounded trcewidth.

Tree decomposition hat eine zunehmende Bedeutung als Werkzeug zur Lösung von Graphenproblemen, bedingt durch wichtige algorithmische Eigenschaften der Klasse der Graphen mit beschränkter treewidth. Ein wichtiges Theo- rem von C`ourcelle [Cou9Ol besagt, dass Eigenschaften eines Graphen die in MSO Logik beschrieben werden können, in linearer Zeit für Graphen mit beschränkter treewidth entschieden werden können. Dies gibt den theoretischen Hintergrund für die tractability vieler Graphenprobleme, intractability im Allgemeinen und für die oben erwähnte Graphenklasse regte es zu vielen Algorithmen für MSO-deflnierbaren Problemen an. Bodlaender schlägt in [Bod971 einen Ansatz vor zum Design von Algorithmen mittels dynamischer Programmierung unter der Verwendung von tree decomposition. Dieser Ansatz stellt eine verallgemeinerte Methode vor, mittels der sich auch bereits vor dieser Arbeit vorgestellte Algorithmen entwerfen hätten lassen, wichtiger jedoch diese Methode kann verwendet werden um neue Algorithmen für eine Vielzahl von Graphenprobleinen zu konstruieren.
In dieser Diplomarbeit haben wir diesen Ansatz untersucht und iniplementiert. Das Ergebnis ist ein System, das Bodlaender`s Methode verwendet und das es erlaubt spezifische Teile des Algorithmuses mittels Plugins zu beschreiben. Um die Verwendbarkeit und Effizienz des Systems einzuschätzen haben wir einen Algorithmus für Dreifärbung als Plugin implementiert.