Diploma Thesis DIP-1508

BibliographyLewandowski, Stefan: Anwendungen für Separatortheoreme auf planaren Graphen.
University of Stuttgart, Faculty of Computer Science, Diploma Thesis No. 1508 (1997).
59 pages, german.
CR-SchemaF.2.1 (Numerical Algorithms and Problems)
F.2.2 (Nonnumerical Algorithms and Problems)
G.1.3 (Numerical Linear Algebra)
G.2.2 (Graph Theory)
Abstract

Eine oft verwendete Strategie zum Entwurf effizienter Algorithmen ist ,,divide-and-conquer``. Dabei wird das betrachtete Problem in zwei (oder mehr) kleinere Teilprobleme zerlegt, die dann rekursiv mit dieser Methode gelöst werden. Die Lösungen der Teilprobleme werden zu einer Lösung des Ausgangsproblems zusammengefügt.

Damit ,,divide-and-conquer`` sinnvoll angewendet werden kann, muß folgendes erfüllt sein: - Die Teilprobleme müssen von gleicher Natur wie das Ausgangsproblem und bzgl. der Problemstellung voneinander unabhängig sein. - Die Teilprobleme müssen signifikant kleiner als das Ausgangsproblem sein. - Der Aufwand zum Finden einer Lösung aus den Lösungen der Teilprobleme muß vergleichsweise gering sein.

Soll ,,divide-and-conquer`` auf Graphenprobleme angewendet werden, so bieten Separatoren eine Möglichkeit, das Ausgangsproblem in unabhängige Teilprobleme zu zerlegen. Sei K eine unter Untergraphenbildung abgeschlossene Graphenklasse (d.h., falls G_1 in K und G_2 Untergraph von G_1 ist, so gilt auch G_2 in K). Die Graphenklasse K erfüllt ein f(n)-Separatortheorem, falls Konstanten a<1 und b>0 existieren, so daß die Knoten jedes Graphen G in K in drei disjunkte Mengen A, B und S so zerlegt werden können, daß keine Kanten Knoten aus A mit Knoten aus B verbinden und weder A noch B mehr als a*n Knoten haben, weiterhin soll die Größe von S durch b*f(n) beschränkt sein. Läßt sich solch eine Zerlegung für alle Graphen G in K schnell finden, so lassen sich für diese Graphen viele Probleme mit ,,divide-and-conquer`` lösen. Der Aufwand zum Zusammenfügen der Teillösungen ist i.a. eine Funktion g(f(n)), so daß f(n) möglichst klein, d.h. zumindest f(n) in o(n), sein sollte.

Lipton & Tarjan stellten 1977 ihr n^(1/2)-Separatortheorem für planare Graphen vor. Bis dahin waren praktikable Separatortheoreme nur für recht spezielle Graphenklassen bekannt, wie z.B. ein 1-Separatortheorem für Bäume (mit a=2/3) und für Gittergraphen ein n^(1/2)-Separatortheorem (ebenfalls mit a=2/3). Planare Graphen hingegen tauchen in vielen praktischen Problemen auf und so sollen hier die Separatortheoreme von Lipton & Tarjan vorgestellt und einige Anwendungen dieser Theoreme dargestellt werden. Die Effizienz dieser Algorithmen soll schließlich noch mit der anderer Algorithmen, die ohne Separatoren arbeiten, verglichen werden.

Full text and
other links
PostScript (2276980 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 dateJuly 17, 1997
   Publ. Computer Science