Increasing distances in graphs

Krause, Stefan

In der vorliegenden Arbeit wird ein spezielles Set Cover Problem studiert. Es ist eng mit minimalen Schnitten in Graphen verbunden, d.h. mit Problemen, bei denen alle Wege zwischen den Knoten eines oder mehrerer gegebener Knotenpaare unterbrochen werden. Im Gegensatz dazu wird hier nur gefordert, dass die kürzesten Wege (bezüglich Einheitslängen) durchtrennt werden. Die Aufgabe besteht also darin, in einem ungerichteten Graphen den Abstand zwischen den Knoten gegebener Paare durch Entfernen einer kostenminimalen Kantenmenge um mindestens 1 zu erhöhen. Das Problem wird als Blocking Shortest Paths bezeichnet. Es werden für einige Spezialfälle polynomielle Algorithmen angegeben, und es wird gezeigt, dass das Problem in den meisten übrigen Fällen NP-vollständig ist. Durch diese Ergebnisse motiviert werden Ansätze zur exakten Lösung mittels ganzzahliger Optimierung sowie mehrere Algorithmen zur approximativen Lösung vorgestellt. Für letztere werden bestmögliche Gütegarantien angegeben oder zumindest eng eingegrenzt. Die besprochenen Algorithmen werden an zufälligen Instanzen getestet. Ergänzend werden extremale Fragen dieses Themenkreises diskutiert.

In this work a special Set Cover problem is studied. It has strong links to Min Cut problems, that is, problems where all paths between vertices of given pairs are to be blocked. Here, on the contrary, we only demand that shortest paths (with unit edge lengths) are disconnected. Therefore the goal is to increase distances of given vertex pairs by at least 1 by removing an edge set having minimum cost. This problem is called blocking shortest paths. For some special cases polynomial time algorithms are given, and it is shown that in most other cases the problem is NP-complete. Motivated by this result we show how to solve this problem exactly using mixed integer programming, and we present approximation algorithms. For the latter one we determine best possible performance guarantees or give at least almost tight bounds. The given algorithms are tested for random instances. In addition extremal problems of this area are discussed.

Vorschau

Zitieren

Zitierform:

Krause, Stefan: Increasing distances in graphs. 2006.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Details anzeigen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export