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

Authors

  • Richard E. Korf University of California, Los Angeles

DOI:

https://doi.org/10.1609/socs.v12i1.18553

Keywords:

Combinatorial Puzzles, Symmetry Handling, External-memory And Parallel Search

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.

Downloads

Published

2021-07-21