A fast randomized LOGSPACE algorithm for graph connectivity

作     者：Feige, U 

作者机构：Department of Applied Math and Computer Science The Weizmann Institute Rehovot 76100 Israel 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (Theor Comput Sci)

年 卷 期：1996年第169卷第2期

页      面：147-160页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Computation theory 

摘      要：We study the relationship between undirected graph reachability and graph connectivity, in the context of randomized LOGSPACE algorithms. Aleluinas et al. [2] show that graph reachability (checking whether there is a path connecting vertices L and F) can be decided in logarithmic space and polynomial time, by starting a random walk at L, and checking whether F is hit within some time limit. The randomized algorithm has one-sided error (with small probability, it fails to determine that L and F are connected). The reachability algorithm may be used in order to decide (with one-sided error) whether a graph is connected, by running it n - 1 times, each time with a different target vertex F. This increases the running time by a factor of n. In this paper we give an alternative randomized LOGSPACE algorithm for graph connectivity. Its running time varies between O(n(2)) steps and O(n(3)) steps, depending on the structure of the input graph. This matches the fastest known RLOGSPACE algorithm for reachability, up to a constant factor. Our algorithm has two-sided error.