Undirecteds-t connectivity in polynomial time and sublinear space |
| |
Authors: | Greg Barnes Walter L Ruzzo |
| |
Affiliation: | (1) Department of Computer Science and Engineering, FR-35, University of Washington, 98195 Seattle, WA, USA |
| |
Abstract: | Thes-t connectivity problem for undirected graphs is to decide whether two designated vertices,s andt, are in the same connected component. This paper presents the first known deterministic algorithms solving undirecteds-t connectivity using sublinear space and polynomial time. Our algorithms provide a nearly smooth time-space tradeoff between depth-first search and Savitch's algorithm. Forn vertex,m edge graphs, the simplest of our algorithms uses spaceO(s),n
1/2log2
n s nlog2
n, and timeO(((m+n)n
2
log2
n)/s). We give a variant of this method that is faster at the higher end of the space spectrum. For example, with space (nlogn), its time bound isO((m+n)logn), close to the optimal time for the problem. Another generalization uses less space, but more time: spaceO( n
1/ logn), for 2![le](/content/x6u3070672130886/xxlarge8804.gif) ![lambda](/content/x6u3070672130886/xxlarge955.gif) log2
n, and timen
O( ). For constant the time remains polynomial. |
| |
Keywords: | undirected connectivity time-space tradeoff |
本文献已被 SpringerLink 等数据库收录! |
|