论文标题
在无原形图的直径周围
Around the diameter of AT-free graphs
论文作者
论文摘要
如果图算法在$ {\ cal o}（m^b）上运行的$ m $ - edge graphs上的$ {\ cal o}（m^b）$ time，则确实是次级算法。 Roditty和Vassilevska Williams（STOC'13）证明，在合理的复杂性假设下，没有真正的次级算法来计算一般图的直径。在这项工作中，我们呈现出关于在某些特殊图类别上计算直径的这种算法存在的积极和负面结果。具体而言，如果有两个之间的三个顶点形成一个小行星三重（AT），则在其中任何两个之间存在一条避免第三个封闭邻居的路径。如果不包含AT，我们将其称为无图形。我们首先证明，对于所有$ m $ - edge at的图形，一个人可以计算真正子限制$ {\ cal o}（m^{3/2}）$ time中的所有偏心。然后，我们将研究扩展到弦图的几个子类（所有这些都以各种方式概括了间隔图），以试图了解哪些无易于图的特性或后者的自然概括都可以帮助设计快速算法在宽图类别上直径问题的快速算法。例如，对于所有具有主要最短路径的和弦图，如果直径至少为四个，则有一种线性时时间算法用于计算直径对。但是，对于具有统治优势的拆分图，在合理的复杂性假设下，没有真正的次级算法来确定直径是$ 2 $还是$ 3 $。
A graph algorithm is truly subquadratic if it runs in ${\cal O}(m^b)$ time on connected $m$-edge graphs, for some positive $b < 2$. Roditty and Vassilevska Williams (STOC'13) proved that under plausible complexity assumptions, there is no truly subquadratic algorithm for computing the diameter of general graphs. In this work, we present positive and negative results on the existence of such algorithms for computing the diameter on some special graph classes. Specifically, three vertices in a graph form an asteroidal triple (AT) if between any two of them there exists a path that avoids the closed neighbourhood of the third one. We call a graph AT-free if it does not contain an AT. We first prove that for all $m$-edge AT-free graphs, one can compute all the eccentricities in truly subquadratic ${\cal O}(m^{3/2})$ time. Then, we extend our study to several subclasses of chordal graphs -- all of them generalizing interval graphs in various ways --, as an attempt to understand which of the properties of AT-free graphs, or natural generalizations of the latter, can help in the design of fast algorithms for the diameter problem on broader graph classes. For instance, for all chordal graphs with a dominating shortest path, there is a linear-time algorithm for computing a diametral pair if the diameter is at least four. However, already for split graphs with a dominating edge, under plausible complexity assumptions, there is no truly subquadratic algorithm for deciding whether the diameter is either $2$ or $3$.
