Treffer: Space-Efficient DFS and Applications to Connectivity Problems: Simpler, Leaner, Faster.

The problem of space-efficient depth-first search (DFS) is reconsidered. A particularly simple and fast algorithm is presented that, on a directed or undirected input graph G = (V , E) with n vertices and m edges, carries out a DFS in O (n + m) time with n + ∑ v ∈ V ≥ 3 ⌈ log 2 (d v - 1) ⌉ + O (log n) ≤ n + m + O (log n) bits of working memory, where d v is the (total) degree of v, for each v ∈ V , and V ≥ 3 = { v ∈ V ∣ d v ≥ 3 } . A slightly more complicated variant of the algorithm works in the same time with at most n + (4 / 5) m + O (log n) bits. It is also shown that a DFS can be carried out in a graph with n vertices and m edges in O (n + m + min { n , m } log ∗ n) time with O(n) bits or in O (n + m) time with either O (n log log (4 + m / n)) bits or, for arbitrary integer k ≥ 1 , O (n log (k) n) bits. These results among them subsume or improve most earlier results on space-efficient DFS. Some of the new time and space bounds are shown to extend to applications of DFS such as the computation of cut vertices, bridges, biconnected components and 2-edge-connected components in undirected graphs. [ABSTRACT FROM AUTHOR]

Copyright of Algorithmica is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)