TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 29.06.2017

isti-logo

Page Content

to Navigation

When can Graph Hyperbolicity be computed in Linear Time?

Till Fluschnik (TU Berlin)

Hyperbolicity measures, in terms of (distance) metrics, how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known practical algorithms for computing the hyperbolicity number of a \(n\)-vertex graph have running time \(O(n^4)\). Exploiting the framework of parameterized complexity analysis, we explore possibilities for “linear-time FPT” algorithms to compute hyperbolicity. For instance, we show that hyperbolicity can be computed in time \(2^{O(k)} + O(n + m)\) (\(m\) being the number of graph edges, \(k\) being the size of a vertex cover) while at the same time, unless the SETH fails, there is no \(2^{o(k)} n^{(2-\epsilon)}\)-time algorithm.

This is joint work with Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, and Nimrod Talmon.

Date
Speaker
Location
Language
29.06.2017
16:15
Till Fluschnik
TEL 512
English

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe