Hyper.
Hyper.
复制标题
超。
DOI：
10.7748/ns.2.11.48.s105
复制
发表时间：
1988
影响因子：
--
通讯作者：
Nimrod Talmon
中科院分区：
文献类型：
--
作者：
T. Fluschnik;Christian Komusiewicz;G. B. Mertzios;A. Nichterlein;R. Niedermeier;Nimrod Talmon
双曲度用（距离）度量来度量一个给定的图离树有多近。由于其与现实世界网络建模的相关性，双曲性在过去几年中得到了深入的研究。不幸的是，用于计算图的双曲数（越小，越像树）的最著名算法的运行时间为O(n)，其中n是图顶点的数量。利用参数化复杂性分析的框架，我们探索了“线性时间FPT”算法计算双曲度的可能性。例如，我们证明了双曲度可以在O(2 +n+m) （m是图边的数目）时间内计算出来，而同时，除非SETH失败，否则不存在2n-time算法。
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), 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 +n+m) (m being the number of graph edges) while at the same time, unless the SETH fails, there is no 2n-time algorithm.