Analyse eines den 4-Zusammenhang zertifizierenden Algorithmus

Zertifikate sind in der Graphentheorie hilfreich um Eigenschaften von Graphen schnell nachweisen zu können. Elmasry, Mehlhorn und Schmidt setzten sich mit 3-Zusammenhang in Hamiltongraphen auseinander und entwickelten ein Zertifikat, welches mittels eines Algorithmus in Laufzeit O(m + n) verifiziert, ob ein Hamiltongraph 3-zusammenhängend ist. Schmidt hat dies 2010 auf allgemeine Graphen mithilfe der Barnett-Grünbaum-Pfade erweitert. Somit gibt es ein Zertifikat für 3-Zusammenhang in Graphen. In dieser Arbeit beschäftigt uns die Frage: Kann man auch ein Zertifikat für 4-Zusammenhang aufstellen? Dabei stützen wir uns auf die Resultate der Arbeiten von Martinov und von Mader bezüglich 4-zusammenhängender Graphen. Ziel ist es, einen vorgegebenen Graphen G aus einem kontraktionskritischen, 4-zusammenhängenden Ausgangsgraphen mittels einer Sequenz den 4-Zusammenhang erhaltenden Kantenexpansionen zu rekonstruieren.

Certificates are useful in graph theory to quickly prove properties of graphs. Elmasry, Mehlhorn and Schmidt studied 3-connection in Hamilton graphs and developed a certificate which verifies whether a Hamilton graph is 3-connected using an algorithm in runtime O(m + n). Schmidt extended this to general graphs using the Barnett-Grünbaum Pfade in 2010. Thus there is a certificate for 3-connected graphs. In this thesis we are concerned with the question: Is it possible to create a certificate for 4-connected graphs? We base this on the results of Martinov's and Mader's work on 4-connected graphs. The goal is to reconstruct a given graph G from a contraction-critical, 4-connected initial graph by using a sequence of edge expansions that preserve the 4-connection.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten