Datenbestand vom 13. Juni 2019

Warenkorb Datenschutzhinweis Dissertationsdruck Dissertationsverlag Institutsreihen     Preisrechner

WICHTIGER HINWEIS
DER VERLAG IST IN DER ZEIT VOM 12.06.2019 BIS 23.06.2019 AUSCHLIESSLICH PER EMAIL ERREICHBAR.

aktualisiert am 13. Juni 2019

ISBN 9783843926980

Euro 72,00 inkl. 7% MwSt


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.