Breadth-depth Search (BDS)
Category: Searching Graphs
Input
An undirected graph $G = (V, E)$ with a numbering on the vertices, and two designated vertices $u$ and $v$.
Problem
Is vertex $u$ visited before vertex $v$ in the breadth-depth first search of $G$ induced by the vertex numbering?
Definitions
A breadth-depth first search (Horowitz and Sahni [1]) starts at a vertex $s$ and visits all children of $s$ pushing them on a stack as the search proceeds. After all of $s$’s children have been visited, the search continues with the vertex on the top of the stack playing the role of $s$.
Status
$\P$-complete (Greenlaw [2]).
Remarks
A reduction from NORCVP is presented in [3] for both undirected and directed graphs. Several other reductions for the problem are described in detail in [1], the main one being from LFDFS.
References
- E. Horowitz and S. Sahni (1978). Fundamentals of Computer Algorithms.
- R. Greenlaw (1993). Breadth-depth search is P-complete.
- R. Greenlaw (1988). The Complexity of Parallel Computations: Inherently Sequential Algorithms and P-Complete Problems.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.3.4.