Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster

DOI10.1007/S00453-019-00629-XMaRDI QIDQ2300733zbMATH OpenOpenAlexWikidataFDO

Authors Torben Hagerup

Publication date 28 February 2020

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.11864

zbMATH Keywords

depth-first searchgraph algorithmsconnectivityspace efficiency

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Data structures (68P05) Searching and sorting (68P10) Connectivity (05C40)

Abstract: 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+su{m}_{vin{V}_{ge3}}lceillo{g}_2(d_v-1)ceil+O(logn)len+m+O(logn)$ bits of working memory, where $d_v$ is the (total) degree of $v$, for each $vinV$, and $V_{ge3}=vinVmid{d}_{v}ge3$. A slightly more complicated variant of the algorithm works in the same time with at most $n+(4/5)m+O(logn)$ bits. It is also shown that a DFS can be carried out in a graph with $n$ vertices and $m$ edges in $O(n+mlo{g}^{\ast }!n)$ time with $O(n)$ bits or in $O(n+m)$ time with either $O(nloglog(4+m/n))$ bits or, for arbitrary integer $kge1$, $O(nlo{g}^{(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.

Recommendations

• Space efficient linear time algorithms for BFS, DFS and applications
• Depth-First Search Using $$O(n)$$ Bits
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Biconnectivity, chain decomposition and \(st\)-numbering using \(O(n)\) bits
• Improved space efficient algorithms for BFS, DFS and applications

Cites work

• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• A simple test on 2-vertex- and 2-edge-connectivity
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Changing base without losing space
• Depth-First Search Using $$O(n)$$ Bits
• Depth-First Search and Linear Graph Algorithms
• Introduction to algorithms.
• Optimal lower bounds for rank and select indexes
• Path-based depth-first search for strong and biconnected components
• Rank-select indices without tears
• Relationships between nondeterministic and deterministic tape complexities
• Space efficient linear time algorithms for BFS, DFS and applications
• Space-efficient Euler partition and bipartite edge coloring
• Space-efficient basic graph algorithms
• Space-efficient biconnected components and recognition of outerplanar graphs
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets

Cited in

(19)

• Approximation in (poly-) logarithmic space
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• A Snap-Stabilizing DFS with a Lower Space Requirement
• Finding strong components using depth-first search
• Improved space efficient algorithms for BFS, DFS and applications
• Space-efficient basic graph algorithms
• Biconnectivity, chain decomposition and \(st\)-numbering using \(O(n)\) bits
• Depth-first search in directed planar graphs, revisited
• Space-efficient vertex separators for treewidth
• Succinct data structure for path graphs
• Simple DFS on the complement of a graph and on partially complemented digraphs
• Sorting and ranking of self-delimiting numbers with applications to tree isomorphism
• Space-efficient fully dynamic DFS in undirected graphs
• scientific article; zbMATH DE number 1798166 (Why is no real title available?)
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Space efficient linear time algorithms for BFS, DFS and applications
• Indexing graph search trees and applications
• Space-efficient biconnected components and recognition of outerplanar graphs
• Space-efficient biconnected components and recognition of outerplanar graphs

This page was built for publication: Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300733)