论文标题
障碍物以更快的直径计算：小行星集
Obstructions to faster diameter computation: Asteroidal sets
论文作者
论文摘要
四肢是一个顶点，因此去除其封闭的邻域不会增加连接组件的数量。令$ext_α$是所有连接图的类的类别，其从模块化分解获得的商图包含不超过$α$成对的非附近末端。我们的主要贡献如下。首先，我们证明可以在确定性$ {\ cal o}（α^3 m^{3/2}）$时间的确定性$ {\ cal o}中计算出每个$ m $ - 边缘图的直径。然后，我们改善了使用有界集团数字的所有图形线性的运行时间。此外，我们可以计算确定性$ {\ cal o}（α^2 m）$ time中所有顶点偏心率的添加$+1 $ -APPROXIMATION。这与一般$ m $ - 边缘图相反，在强度指数时间假设（SETH）下，一个人无法计算$ {\ cal o}（\ cal o}（m^{2-ε}）$时间的直径，任何$ε> 0 $。 作为我们主要结果的重要特殊情况，我们得出了$ {\ cal o}（m^{3/2}）$ - 时间算法，用于直径的精确直径计算，至少六个，至少六个，$ {\ cal o}（\ cal o}（k^3m^{3/2}} $ - 时间 - 时间algorith in GrageS $ k $ k in GrageS $ k $ k in GrageS $ k in GrageS $ k in Grage n os Grage in Groge in Groge in $ k in $ k n os Grage os n os Grage os n os Grage os n os Grage in $ k in $ k.我们最终为有界小行星数的弦图提供了一种改进的算法，以及我们的结果部分扩展到具有限制性基数的主导目标的所有图形的较大类。在合理的复杂性假设下，纸张中的时间上限本质上是最佳的。
An extremity is a vertex such that the removal of its closed neighbourhood does not increase the number of connected components. Let $Ext_α$ be the class of all connected graphs whose quotient graph obtained from modular decomposition contains no more than $α$ pairwise nonadjacent extremities. Our main contributions are as follows. First, we prove that the diameter of every $m$-edge graph in $Ext_α$ can be computed in deterministic ${\cal O}(α^3 m^{3/2})$ time. We then improve the runtime to linear for all graphs with bounded clique-number. Furthermore, we can compute an additive $+1$-approximation of all vertex eccentricities in deterministic ${\cal O}(α^2 m)$ time. This is in sharp contrast with general $m$-edge graphs for which, under the Strong Exponential Time Hypothesis (SETH), one cannot compute the diameter in ${\cal O}(m^{2-ε})$ time for any $ε> 0$. As important special cases of our main result, we derive an ${\cal O}(m^{3/2})$-time algorithm for exact diameter computation within dominating pair graphs of diameter at least six, and an ${\cal O}(k^3m^{3/2})$-time algorithm for this problem on graphs of asteroidal number at most $k$. We end up presenting an improved algorithm for chordal graphs of bounded asteroidal number, and a partial extension of our results to the larger class of all graphs with a dominating target of bounded cardinality. Our time upper bounds in the paper are shown to be essentially optimal under plausible complexity assumptions.
