Space-efficient fully dynamic DFS in undirected graphs
Summary: Depth-first search (DFS) is a well-known graph traversal algorithm and can be performed in \(O(n + m)\) time for a graph with \(n\) vertices and \(m\) edges. We consider the dynamic DFS problem, that is, to maintain a DFS tree of an undirected graph \(G\) under the condition that edges and vertices are gradually inserted into or deleted from \(G\). We present an algorithm for this problem, which takes worst-case \(O(\sqrt{mn} \cdot \operatorname{polylog}(n))\) time per update and requires only \((3 m + o(m)) \log n\) bits of space. This algorithm reduces the space usage of dynamic DFS algorithm to only 1.5 times as much space as that of the adjacency list of the graph. We also show applications of our dynamic DFS algorithm to dynamic connectivity, biconnectivity, and 2-edge-connectivity problems under vertex insertions and deletions.
- A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- An improved algorithm for incremental DFS tree in undirected graphs
- Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
- A data structure for dynamic trees
- A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
- An improved algorithm for incremental DFS tree in undirected graphs
- Dynamic connectivity: connecting to networks and geometry
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Dynamically switching vertices in planar graphs
- Fast construction of wavelet trees
- Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
- scientific article; zbMATH DE number 2079421 (Why is no real title available?)
- scientific article; zbMATH DE number 1512678 (Why is no real title available?)
- Improved data structures for the orthogonal range successor problem
- Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
- Incremental DFS algorithms: a theoretical and experimental study
- On Dynamic DFS Tree in Directed Graphs
- Range predecessor and Lempel-Ziv parsing
- Self-indexing based on LZ77
- Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
- The incremental maintenance of a depth-first-search tree in directed acyclic graphs
- Wavelet trees for all
- Fault tolerant depth first search in undirected graphs: simple yet efficient
- Dynamic subtrees queries revisited: the depth first tour tree
- On Dynamic DFS Tree in Directed Graphs
- A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
- scientific article; zbMATH DE number 1798166 (Why is no real title available?)
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
- Indexing graph search trees and applications
- Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- A Snap-Stabilizing DFS with a Lower Space Requirement
- Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries
This page was built for publication: Space-efficient fully dynamic DFS in undirected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2312405)
