ISSN:
1420-8954
Keywords:
undirected connectivity
;
time-space tradeoff
;
05C40
;
05C85
;
68Q05
;
68Q10
;
68Q15
;
68Q20
;
68Q25
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
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≤λ≤log2 n, and timen O(λ). For constant λ the time remains polynomial.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01202039
Permalink