Depth-first search is inherently sequential

Published

Journal Article

This paper concerns the computational complexity of depth-first search. Suppose we are given a rooted graph G with fixed adjacency lists and vertices u, v. We wish to test if u is first visited before v in depth-first search order of G. We show that this problem, for undirected and directed graphs, is complete in deterministic polynomial time with respect to deterministic log-space reductions. This gives strong evidence that depth-first search ordering can be done neither in deterministic space (log n)c nor in parallel time (log n)c, for any constant c > 0. © 1985.

Full Text

Duke Authors

Cited Authors

  • Reif, JH

Published Date

  • June 12, 1985

Published In

Volume / Issue

  • 20 / 5

Start / End Page

  • 229 - 234

International Standard Serial Number (ISSN)

  • 0020-0190

Digital Object Identifier (DOI)

  • 10.1016/0020-0190(85)90024-9

Citation Source

  • Scopus