Finding the Exact Diameter of a Graph with Partial Breadth-First Searches

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Long Papers

The diameter of a graph is the longest shortest path between two nodes. This paper presents an improved algorithm for finding the exact diameter of an undirected graph. Rather than performing complete breadth-first searches, these searches can be terminated early. The algorithm is readily parallelized, and is used to find the diameters of 4-peg Tower of Hanoi problem-space graphs with up to 18 discs. Performance improvements range from a factor of almost 2 to 5.88 over the previous state of the art.

10.1609/socs.v12i1.18553