Space-Efficient Fully Dynamic DFS in Undirected Graphs

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 ( m n · 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.

• Publication year

  2019

• Venue

  Algorithms

• Publication date

  2019-02-27

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.3390/a12030052
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Braided distributivity

  2018cited by this paper
• Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient

  2018influential reference
• Incremental DFS algorithms: a theoretical and experimental study

  2017cited by this paper
• Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs

  2017cited by this paper
• Incremental Algorithm for Maintaining a DFS Tree for Undirected Graphs

  2017influential reference
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs

  2017influential reference
• An Improved Algorithm for Incremental DFS Tree in Undirected Graphs

  2016influential reference
• Improved Algorithms for Maintaining DFS Tree in Undirected Graphs

  2016influential reference
• On Dynamic DFS Tree in Directed Graphs

  2015cited by this paper
• Dynamic DFS in Undirected Graphs: breaking the O(m) barrier

  2015influential reference
• Range Predecessor and Lempel-Ziv Parsing

  2015cited by this paper
• Wavelet trees for all

  2012cited by this paper
• Self-indexing Based on LZ77

  2011influential reference
• Improved data structures for the orthogonal range successor problem

  2011cited by this paper
• Dynamic Connectivity: Connecting to Networks and Geometry

  2008cited by this paper
• Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets

  2007cited by this paper
• High-order entropy-compressed text indexes

  2003cited by this paper
• Dynamically Switching Vertices in Planar Graphs

  2000cited by this paper
• The LCA Problem Revisited

  2000cited by this paper
• Compact pat trees

  1998cited by this paper
• The Incremental Maintenance of a Depth-First-Search Tree in Directed Acyclic Graphs

  1997cited by this paper
• Space-efficient static trees and graphs

  1989cited by this paper
• A data structure for dynamic trees

  1981cited by this paper

• Recent Advances in Efficient Dynamic Graph Processing

  2025cites this paper
• Discovering Important Nodes of Complex Networks Based on Laplacian Spectra

  2023cites this paper
• Fault Tolerant Depth First Search in Undirected Graphs: Simple Yet Efficient

  2022influential citation
• Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide

  2021cites this paper
• Editorial: Special Issue on Efficient Data Structures

  2019cites this paper