When can graph hyperbolicity be computed in linear time?

DOI10.1007/978-3-319-62127-2_34MaRDI QIDQ5920105zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Till Fluschnik, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, Nimrod Talmon

Publication date 22 September 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.06503, http://dro.dur.ac.uk/22111/1/22111.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: 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 algorithms for computing the hyperbolicity number of a graph (the smaller, the more tree-like) have running time $O(n^4)$, where $n$ is the number of graph vertices. 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 $O(2^{O(k)}+n+m)$ ($m$ being the number of graph edges) while at the same time, unless the SETH fails, there is no $2^{o(k)}{n}^2$-time algorithm.

Recommendations

• When can graph hyperbolicity be computed in linear time?
• Applying clique-decomposition for computing Gromov hyperbolicity
• On computing the hyperbolicity of real-world graphs
• On computing the Gromov hyperbolicity
• Fast approximation and exact computation of negative curvature parameters of graphs

Cited in

(12)

• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Enumeration of Far-apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation
• Fast approximation and exact computation of negative curvature parameters of graphs
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• Fast approximation of centrality and distances in hyperbolic graphs
• Applying clique-decomposition for computing Gromov hyperbolicity
• Fast approximation and exact computation of negative curvature parameters of graphs
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• On computing the hyperbolicity of real-world graphs
• On computing the Gromov hyperbolicity
• On adaptive algorithms for maximum matching
• Computing graph hyperbolicity using dominating sets

This page was built for publication: When can graph hyperbolicity be computed in linear time?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5920105)