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

J. Kiniwa (Japan)


depthfirst traversal, decreasing backtracking, probability of taking a shortcut, distributed depthfirst search


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:

Go Back