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

Abstract

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.