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.
Categories: cs.DS