Options
Effiziente Extraktion von Kuratowski-Teilgraphen
Publikationstyp
Master Thesis
Date Issued
2007-03-16
Sprache
German
Author(s)
Title Granting Institution
TU Dortmund
Place of Title Granting Institution
Dortmund
Examination Date
2007
TORE-URI
First published in
Number in series
2007,4
Citation
Masterarbeit, Fachbereich Informatik der Universität Dortmund: 2007,4 (2007)
Publisher
Techn. Univ. Dortmund
Ein Graph ist nach dem Satz von Kuratowski genau dann planar, wenn er keine Kuratowski-Subdivisions enth\"alt. Eine einzelne davon kann von modernen Planarit\"atstests bei nicht planaren Eingabegraphen in Linearzeit extrahiert werden. Allerdings existieren Anwendungen, die nicht nur eine, sondern m\"oglichst viele dieser Kuratowski-Subdivisions ben\"otigen. Dazu geh\"oren Branch-and-Cut-Algorithmen f\"ur einige NP-schwere Probleme, wie beispielsweise die Kreuzungsminimierung oder auch verschiedene Varianten des Maximum Planar Subgraph Problems. Die Kuratowski-Subdivisions erm\"oglichen dort die Berechnung von zus\"atzlichen nebenbedingungen einer LP-Relaxierung. Dabei ist es w\"unschenswert, dass die Kuratowski-Subdivisions paarweise entweder
m\"oglichst viele Kanten gemeinsam haben oder weitgehend kantendisjunkt sind.
In dieser Diplomarbeit wird ein Algorithmus entworfen und analysiert, der mehrere Kuratowski-Subdivisions in linearer Zeit O(n + m + Sum_(K in S) |E(K)|) extrahieren kann, wobei S die Menge der gefundenen Kuratowski-Subdivisions ist. Dieser Algorithmus stellt eine Erweiterung des aktuellen Planarit\"atstests von Boyer und Myrvold dar und kann zus\"atzlich so modifiziert werden, dass entweder m\"oglichst \"ahnliche oder m\"oglichst verschiedene Kuratowski-Subdivisions ausgegeben werden. Die Laufzeit des Algorithmus ist dabei asymptotisch optimal. Aus diesem Algorithmus wird ein zweiter Ansatz entwickelt, der in der Praxis mehr Kuratowski-Subdivisions extrahieren kann, daf\"ur aber zu einer superlinearen Laufzeit f\"uhrt. Beide Verfahren werden implementiert und deren Praxistauglichkeit verglichen.
m\"oglichst viele Kanten gemeinsam haben oder weitgehend kantendisjunkt sind.
In dieser Diplomarbeit wird ein Algorithmus entworfen und analysiert, der mehrere Kuratowski-Subdivisions in linearer Zeit O(n + m + Sum_(K in S) |E(K)|) extrahieren kann, wobei S die Menge der gefundenen Kuratowski-Subdivisions ist. Dieser Algorithmus stellt eine Erweiterung des aktuellen Planarit\"atstests von Boyer und Myrvold dar und kann zus\"atzlich so modifiziert werden, dass entweder m\"oglichst \"ahnliche oder m\"oglichst verschiedene Kuratowski-Subdivisions ausgegeben werden. Die Laufzeit des Algorithmus ist dabei asymptotisch optimal. Aus diesem Algorithmus wird ein zweiter Ansatz entwickelt, der in der Praxis mehr Kuratowski-Subdivisions extrahieren kann, daf\"ur aber zu einer superlinearen Laufzeit f\"uhrt. Beide Verfahren werden implementiert und deren Praxistauglichkeit verglichen.
Subjects
TU Dortmund
DDC Class
510: Mathematik