ISBN 9783843927345

978-3-8439-2734-5, Reihe Informatik

Andrea Jaax
Der GapSet Algorithmus Ein parallelisierbarer Algorithmus zur Berechnung minimaler Schnitte

266 Seiten, Dissertation Universität Trier (2016), Hardcover, A5

Zusammenfassung / Abstract

In dieser Arbeit wird der GapSet Algorithmus präsentiert. Dies ist ein neuer Algorithmus, der zur Berechnung minimaler Schnitte in Graphen entwickelt und implementiert wurde und stellt eine Verallgemeinerung des Algorithmus von Hao und Orlin dar. Der flussbasierte Minimum Cut Algorithmus baut auf drei Charakteristika auf: der Informations–Wiederverwendung, der Partitionierung der Knotenmenge in GapSets und der Technik Flussverdopplung. Die neuen Erkenntnisse der Entstehung von GapSets und deren Eigenschaften, sowie die Technik Flussverdopplung bieten ein besseres Verständnis dieser Algorithmen und werden zur Entwicklung des GapSet Algorithmus verwendet. Die Komplexität dieses Algorithmus beträgt O(n^2 √m). Er gehört somit zu den schnellsten theoretischen Minimum Cut Algorithmen.

Neben der theoretischen Analyse des Problems und des neuen GapSet Algorithmus gehen wir genauer auf dessen effiziente Implementierung ein. Durch die Auswertung ausführlicher praktischer Experimente wird ein GapSet Algorithmus entwickelt, welcher für alle untersuchten Eingabeinstanzen so effizient wie möglich arbeitet. Weitere Experimente zeigen, dass die Performance des GapSet Algorithmus für fast alle Eingabeinstanzen den minimalen Schnitt schneller, als alle uns bekannten Implementierungen von Minimum Cut Algorithmen, berechnet. Die Entstehung von GapSets führt außerdem zu einer weiteren Neuheit. Sie bietet die Möglichkeit, den Algorithmus auf eine einfache Weise zu parallelisieren und die praktischen Laufzeiten weiter zu verbessern. Die Laufzeiten des parallelen GapSet Algorithmus sind mindestens genau so schnell wie die der seriellen Variante und sind in einigen Fällen sogar deutlich schneller. Nach unserem Kenntnisstand ist dies der bisher einzige parallele Minimum Cut Algorithmus, der eine bessere Performance als die effizientesten seriellen Algorithmen besitzt.