direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

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.

 

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

Back to the research colloquium site.

Zusatzinformationen / Extras