direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Zusatzinformationen / Extras