Uni Köln / ZAIK / AFS / Lehre / Dienstagseminar / Gregor Pardella - 27. Januar 2009

Gregor Pardella
Universität zu Köln

Ein schneller max-cut Algorithmus für planare Graphen - F. Liers und G. Pardella

Sei G=(V,E) ein (gewichteter) Graph mit Knotenmenge V und Kantenmenge E. Das max-cut Problem besteht darin, eine Partitionierung der Knotenmenge V in zwei Knotenmengen W \subseteq V und V \setminus W zu finden, so dass die Summe der Kantengewichte w(e) der Kanten e=(v,w) mit v \in V \setminus W, w \in W maximal ist.

Partitionierungsprobleme bzw. Schnittprobleme finden sich in vielfältigen Anwendungsproblemen. Darunter sind zum Beispiel VIA Minimierung im Schaltkreisentwurf, Physik von ungeordneten Systemen oder auch in der Funktionssicherheit von Netzwerken.

Für beliebig gewichtete allgemeine Graphen ist das max-cut Problem (und durch Vorzeicheninvertierung der Kantengewichte auch das min-cut Problem) NP-schwer. Jedoch ist es für gewisse Graphklassen polynomiell lösbar, insbesondere existieren diverse polynomielle Lösungsstrategien für planare Graphen.

In diesem Vortrag präsentieren wir einen neuen schnellen Algorithmus für das max-cut Problem auf beliebig gewichteten planaren Graphen.

Die Laufzeit unseres Verfahrens kann mit O(|V|^{1.5}log|V|) im schlimmsten Fall abgeschätzt werden. Diese Laufzeitschranke entspricht der des Verfahrens von Shih, Wu und Kuo, welche den derzeit schnellsten Algorithmus für das Problem vorgestellt haben. Jedoch arbeitet unsere Methode auf einem wesentlich kleineren Hilfsgraphen, welcher in linearer Zeit berechnet werden kann und eine einfache Struktur aufweist. Da die meiste Rechenzeit auf die Berechnung des Matchings im Hilfsgraphen abfällt, ist es einsichtig, dass unser Verfahren in der Praxis schneller und ressourcenschonender ist. Wir können mit unserem Programm Schnitte in grossen realistischen sowie zufälligen Instanzen mit über 106 Knoten effizient zu berechnen.