We develop a linear time algorithm for finding the diameter of an AT-free graph. Furthermore, we update the definition of polar sets and develop new properties of polar sets for (weak) dominating pair graphs. We prove that the problems of finding simplicial vertices and finding triangles in general graphs can be accomplished in O(n^2) based on existing reductions of these problems to the problem of finding diameter in AT-free graphs. We improve the best-known run-time complexities of several graph theoretical problems.

翻译：我们为寻找AT-free图形的直径开发了线性时间算法。 此外,我们更新了对极组的定义,并开发了极组的新的属性,用于(较弱的)支配双对图。我们证明,在O(n)2中,根据这些问题对AT-free图形中直径的发现问题的现有减少,在一般图形中找到简化的脊椎和三角形的问题可以在O(n)2中解决。我们改进了一些图表理论问题中最著名的运行时复杂性。