2022/08/31 by Oleksiy Al-Saadi, Al-saadi, Oleksiy, Jitender S. Deogun +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2209.00110
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(n2) 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.