Name
Abstract | ||
|---|---|---|
We provide algorithms performing Depth-First Search (DFS) on a directed or undirected graph with n vertices and m edges using only O(n) bits. One algorithm uses O(n) bits and runs in O(mlog n) time. Another algorithm uses n+ o(n) bits and runs in polynomial time. Furthermore, we show that DFS on a directed acyclic graph can be done in space n/2(Omega(root log n)) and in polynomial time, and we also give a simple linear-time O(log n)-space algorithm for the depth-first traversal of an undirected tree. Finally, we also show that for a graph having an O(1)-size feedback set, DFS can be done in O(log n) space. Our algorithms are based on the analysis of properties of DFS and applications of the s-t connectivity algorithms due to Reingold and Barnes et al., both of which run in sublinear space. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-13075-0_44 | ALGORITHMS AND COMPUTATION, ISAAC 2014 |
DocType | Volume | ISSN |
Conference | 8889 | 0302-9743 |
Citations | PageRank | References |
7 | 0.52 | 12 |
Authors | ||
9 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tetsuo Asano | 1 | 1448 | 229.35 |
| Taisuke Izumi | 2 | 284 | 39.02 |
| Masashi Kiyomi | 3 | 204 | 17.45 |
| Matsuo Konagaya | 4 | 9 | 1.27 |
| Hirotaka Ono | 5 | 400 | 56.98 |
| Yota Otachi | 6 | 161 | 37.16 |
| Pascal Schweitzer | 7 | 34 | 6.39 |
| Jun Tarui | 8 | 134 | 16.16 |
| Ryuhei Uehara | 9 | 528 | 75.38 |