An Extended Depth-first Search with an Application to Distributed Algorithms – How to Decrease Backtracking

J. Kiniwa (Japan)

Keywords

depth-first traversal, decreasing backtracking, probability of taking a shortcut, distributed depth-first search

Abstract

This paper presents a new method for decreasing back tracking in depth-first traversal. It shows conditions of returning to the starting node without backtracking. The method, however, cannot always succeed in general be cause there are several choices to explore an unvisited adjacent node. Some properties concerning successful probabilities in complete graphs, rings and simple series parallel graphs can be evaluated. Finally, it shows an application of our method to distributed depth-first search.

Important Links:

• DOI:
• From Proceeding (368) Networks, Parallel and Distributed Processing, and Applications - 2002

Go Back