Student Thesis STUD-1610

BibliographyLange, Sven: Separatoren von planaren Graphen: Implementierung und Anwendung eines Algorithmus von Lipton und Tarjan.
University of Stuttgart, Faculty of Computer Science, Student Thesis No. 1610 (1997).
162 pages, german.
CR-SchemaD.2.5 (Software Engineering Testing and Debugging)
D.2.8 (Software Engineering Metrics)
F.2.m (Analysis of Algorithms and Problem Complexity Miscellaneous)
G.2.2 (Graph Theory)
KeywordsSeparator; planare Graphen
Abstract

Der von Lipton und Tarjan präsentierte Separator--Satz partitioniert die Knotenmenge $E$ eines planaren Graphen $G = (V, E)$ in drei Mengen $A$, $B$ und $C$. Die Untergraphen, die durch $A$ und $B$ induziert werden, sind durch keine Kante verbunden und deutlich kleiner als $G$. Damit eröffnet dieser Separator--Satz die Klasse der planaren Graphen für Divide--and--Conquer--Verfahren.

Dieser Satz wird innerhalb der vorliegenden Arbeit bewiesen. Der Beweis führt zu einem Algorithmus, dessen Herleitung und Implementierung ausführlich dokumentiert werden. Es wird gezeigt, daß der Algorithmus in Linearzeit abläuft. Praxistests der im Rahmen dieser Arbeit erstellten Implementierung haben dieses Ergebnis bestätigt. Zur Darstellung der entsprechenden Datenstrukturen (z.B.\ Graphen und Mengen) konnte das Programmpaket LEDA erfolgreich -- wenn auch mit größeren Problemen -- eingesetzt werden.

Full text and
other links
PostScript (2952917 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Computer Science, Theoretical Computer Science
Entry dateMay 20, 1997
   Publ. Computer Science