Name
Abstract | ||
|---|---|---|
We present a spectrum of randomized time-space tradeoffs for solving directed graph connectivity or STCONN in small space. We use a strategy parameterized by a parameter k that uses k pebbles and performs short random walks of length n(1/k) using a probabilistic counter. We use this to get a family of algorithms that ranges between log(2) n and log n in space and 2(log2) (n) and n(n) in running time. Our approach allows us to look at Savitch's algorithm and the random walk algorithm as two extremes of the same basic divide and conquer strategy. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-24597-1_18 | LECTURE NOTES IN COMPUTER SCIENCE |
Keywords | Field | DocType |
random walk,spectrum,directed graph,divide and conquer | Space time,Binary logarithm,Discrete mathematics,Combinatorics,Parameterized complexity,Random walk,Directed graph,Divide and conquer algorithms,Probabilistic logic,Connectivity,Mathematics | Conference |
Volume | ISSN | Citations |
2914 | 0302-9743 | 1 |
PageRank | References | Authors |
0.37 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Parikshit Gopalan | 1 | 1186 | 61.52 |
| Richard J. Lipton | 2 | 6412 | 1796.57 |
| Aranyak Mehta | 3 | 1216 | 82.81 |