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

DOI10.1007/S00453-019-00629-XzbMATH Open1435.68405arXiv1805.11864OpenAlexW2977205563WikidataQ127205061 ScholiaQ127205061MaRDI QIDQ2300733FDOQ2300733

Authors: Torben Hagerup 

Publication date: 28 February 2020

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (19)

• 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
• Title not available (Why is that?)
• 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
• Approximation in (poly-) logarithmic space

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)