Browsing by browse.metadata.tuhhjournals "Algorithm Engineering Report"
Now showing1 - 1 of 1
Results Per Page
Sort Options
- Some of the metrics are blocked by yourconsent settings
Publication without files Effiziente Extraktion von Kuratowski-TeilgraphenEin 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.Publicationtype: Master ThesisThesistype: masterThesisCitation Publisher Version:Masterarbeit, Fachbereich Informatik der Universität Dortmund: 2007,4 (2007)66