Increasing distances in graphs

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.