首页 | 本学科首页   官方微博 | 高级检索  
     


Depth-first search is inherently sequential
Authors:John H Reif
Affiliation:

Center for Research in Computing Technology, Aiken Computation Laboratory, Division of Applied Science, Harvard University, Cambridge, MA 02138, U.S.A.

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.
Keywords:Depth-first search  parallel computation  polynomial time complete
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号