TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 05.02.2015

isti-logo

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.

Date
Speaker
Location
Language
05.02.2015
16:15
André Nichterlein
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe