TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 16.05.2019

isti-logo

Page Content

to Navigation

Parameterized Complexity of Diameter

Matthias Bentert (TU Berlin)

 

Diameter—the task of computing the length of a longest shortest path—is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no O(n^1.99)-time algorithm even in sparse graphs [Roditty and Williams, 2013]. To circumvent this lower bound we aim for algorithms with running time f(k)(n + m) where k is a parameter and f is a function as small as possible. We investigate which parameters allow for such running times. To this end, we systematically explore a hierarchy of structural graph parameters.

 

Date
Speaker
Location
Language
16.05.2019
16:15
Matthias Bentert
TEL 512
English

Back to the research colloquium site.

To top

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe