Finding the Exact Diameter of a Graph with Partial Breadth-First Searches
DOI:
https://doi.org/10.1609/socs.v12i1.18553Keywords:
Combinatorial Puzzles, Symmetry Handling, External-memory And Parallel SearchAbstract
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.Downloads
Published
2021-07-21
Issue
Section
Long Papers