PARALLEL ALGORITHMS FOR DEPTH-1ST SEARCHES .1. PLANAR GRAPHS

作     者：SMITH, JR 

作者机构：Drexel Univ. Philadelphia PA 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1986年第15卷第3期

页      面：814-830页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Computing Parallel architecture 

摘      要：This paper presents an unbounded-parallel algorithm for performing a depth-first search of a planar undirected graph. The algorithm uses O (n super!! 4 ) processors and executes in O (log super!! 3 n )-time. It had previously been conjectured that the problem of computing a depth-first spanning tree was inherently sequential .