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.
Back to the research colloquium site.