direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Finding the Most Vital Edges for Shortest Paths - Algorithms and Complexity for Selected Graph Classes

Maximilian J. Stahlberg (TU Berlin)


I present a summary of my bachelor thesis where I study the NP-hard problem of finding the most vital edges for shortest paths between two terminals of an undirected graph, that are a small number of edges whose deletion increases the distance between the terminals significantly. My thesis evaluates several variants of the associated decision problem with respect to their computational complexity on restricted graph classes. In the presentation I will introduce the problem variants and the examined graph classes and provide either hardness results or algorithms for selected scenarios.


Maximilian J. Stahlberg
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras