ISBN 9783843926980

978-3-8439-2698-0, Reihe Informatik

Andrea Oversberg
On Square Roots of Graphs

165 Seiten, Dissertation Universität Köln (2015), Softcover, A5

Zusammenfassung / Abstract

Die Fragestellung, ob ein gegebener Graph eine Quadratwurzel besitzt und falls ja, eine solche zu finden, ist ein etabliertes Problem der Graphentheorie.

Wir liefern polynomielle Algorithmen zur Lösung des Problems für Inputgraphen, welche Kantengraphen, k-split Graphen oder Graphen mit Cliquenzahl kleiner k für Werte von k = 1, ..., 4 sind.

Des Weiteren geben wir einen polynomiellen Algorithmus an, der für allgemeine Inputgraphen entscheidet, ob eine ptolemäische Quadratwurzel existiert und falls ja, eine solche mit minimaler Kantenzahl berechnet.