TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 12.05.2016

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

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

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe