Publications [#237097] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH, Depth-first search is inherently sequential, Information Processing Letters, vol. 20 no. 5 (June, 1985), pp. 229-234, Elsevier BV, ISSN 0020-0190 [pdf], [doi]
   (last updated on 2026/01/15)

   Abstract:
   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.