TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 12.05.2016

isti-logo

Page Content

to Navigation

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.

 

Date
Speaker
Location
Language
12.05.2016
16:15
Maximilian J. Stahlberg
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe