← All Problems
Open

Directed or Undirected Depth-first Search (DFS)

Category: Network Flows
Tags:
RNC

Input

A graph $G = (V, E)$ and a vertex $s$.

Problem

Construct the depth-first search numbering of $G$ starting from vertex $s$.

Status

Open (Aggarwal and Anderson [1], Aggarwal, Anderson, and Kao [2]).

Remarks

$\mathsf{RNC}$ algorithms are now known for both the undirected [1] and directed [2] cases, subsuming earlier $\mathsf{RNC}$ results for planar graphs (Smith [3]). For directed acyclic graphs, DFS is in $\NC$ (de la Torre and Kruskal [4][5], Greenlaw [6]).

References

  1. A. Aggarwal and R. J. Anderson (1988). A Random NC algorithm for depth first search.
  2. A. Aggarwal, R. J. Anderson, and M.-Y. Kao (1990). Parallel depth-first search in general directed graphs.
  3. J. R. Smith (1986). Parallel algorithms for depth first searches I: Planar graphs.
  4. P. de la Torre and C. P. Kruskal (1989). Fast parallel algorithms for all sources lexicographic search and path finding problems.
  5. P. de la Torre and C. P. Kruskal (1991). Fast and efficient parallel algorithms for single source lexicographic depth-first search, breadth-first search and topological-first search.
  6. R. Greenlaw (1992). A model classifying algorithms as inherently sequential with applications to graph searching.
  7. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.9.2.

Related Problems