New Bounds for Approximating Extremal Distances in Undirected Graphs
New Bounds for Approximating Extremal Distances in Undirected Graphs
复制标题
无向图中近似极值距离的新界限
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Romeo Rizzi
中科院分区：
文献类型：
--
作者：
Massimo Cairo;R. Grossi;Romeo Rizzi
我们提供了一个新的界限的近似极值距离（直径，半径，和偏心率的所有节点）的无向图的n个节点和m条边。首先，我们证明了在Impagliazzo，Paturi和赞内[JCSS 01]的强指数时间假设（SETH）下，对于任意e，Δ > 0，在O（m2-Δ）时间内不可能得到直径的（3/2 - e）-近似或所有偏心率的（5/3 - e）-近似，即使在近似中允许一个常数的加法项。其次，我们提出了一个算法方案，给出了一个（2 - 1/2k）-近似的直径和半径和（3 - 4/（2k + 1））-近似的所有偏心率在O（mn 1/k+1）的期望时间，任何k ≥ 0。对于k ≥ 2，这给出了一个以前未知的边界族，并且随着k的增长接近线性运行时间。第三，我们观察到直径的近似和h-支配集之间的联系，h-支配集是距离其他节点≤ h的节点的子集。我们给这些集的大小的界限，与直径。
We provide new bounds for the approximation of extremal distances (the diameter, the radius, and the eccentricities of all nodes) of an undirected graph with n nodes and m edges. First, we show under the Strong Exponential Time Hypothesis (SETH) of Impagliazzo, Paturi and Zane [JCSS01] that it is impossible to get a (3/2 -- e)-approximation of the diameter or a (5/3 -- e)-approximation of all the eccentricities in O(m2--Δ) time for any e, Δ > 0, even allowing for a constant additive term in the approximation. Second, we present an algorithmic scheme that gives a (2 -- 1/2k)-approximation of the diameter and the radius and a (3 -- 4/(2k + 1))-approximation of all eccentricities in O(mn1/k+1) expected time for any k ≥ 0. For k ≥ 2, this gives a family of previously unknown bounds, and approaches near-linear running time as k grows. Third, we observe a connection between the approximation of the diameter and the h-dominating sets, which are subsets of nodes at distance ≤ h from every other node. We give bounds for the size of these sets, related with the diameter.