TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 05.02.2015


Page Content

to Navigation

A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths

Dr. rer. nat. André Nichterlein (TU Berlin)

We study the NP-hard Shortest Path Most Vital Edges problem arising in the context of analyzing network robustness. For an undirected graph with positive integer edge lengths and two designated vertices s and t, the goal is to delete as few edges as possible in order to increase the length of the (new) shortest st-path as much as possible. This scenario has been mostly studied from the viewpoint of approximation algorithms and heuristics, while we particularly introduce a parameterized and multivariate point of view. We derive refined tractability as well as hardness results, and identify numerous directions for future research. Among other things, we show that increasing the shortest path length by at least one is much easier than to increase it by at least two.

André Nichterlein
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe