论文标题
直径在无原形图上的复杂性是线性的
Complexity of diameter on AT-free graphs is linear
论文作者
论文摘要
我们开发了一种线性时间算法，用于查找小行星三重（无AT）图的直径。此外，我们更新了极地对的定义，并为（弱）主导图开发了极性对的新属性。我们证明，可以基于现有的减少对无atter图中查找直径的问题来实现一般图中计算简单顶点的问题。我们改善了几个图理论问题的最著名的运行时复杂性。
We develop a linear time algorithm for finding the diameter of an asteroidal triple-free (AT-free) graph. Furthermore, we update the definition of polar pairs and develop new properties of polar pairs for (weak) dominating pair graphs. We prove that the problem of computing a simplicial vertex in a general graph can be accomplished in O(n^2) based on an existing reduction to the problem of finding diameter in an AT-free graph. We improve the best-known run-time complexities of several graph theoretical problems.
