Dynamic DFS in undirected graphs: breaking the O(m) barrier

DOI10.1137/1.9781611974331.CH52MaRDI QIDQ4575631zbMATH OpenOpenAlexFDO

Authors Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, Shahbaz Khan

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Abstract: Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes $O(m+n)$ time to build a DFS tree for a given undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges. We address the problem of maintaining a DFS tree when the graph is undergoing {em updates} (insertion and deletion of vertices or edges). We present the following results for this problem. (a) Fault tolerant DFS tree: There exists a data structure of size $O(mpolylogn)$ such that given any set $calF$ of failed vertices or edges, a DFS tree of the graph $GsetminuscalF$ can be reported in $O(n|calF|polylogn)$ time. (b) Fully dynamic DFS tree: There exists a fully dynamic algorithm for maintaining a DFS tree that takes worst case $O(sqrtmnpolylogn)$ time per update for any arbitrary online sequence of updates. (c) Incremental DFS tree: Given any arbitrary online sequence of edge insertions, we can maintain a DFS tree in $O(npolylogn)$ worst case time per edge insertion. These are the first $o(m)$ worst case time results for maintaining a DFS tree in a dynamic environment. Moreover, our fully dynamic algorithm provides, in a seamless manner, the first deterministic algorithm with $O(1)$ query time and $o(m)$ worst case update time for the dynamic subgraph connectivity, biconnectivity, and 2-edge connectivity.

Recommendations

• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Space-efficient fully dynamic DFS in undirected graphs
• An improved algorithm for incremental DFS tree in undirected graphs
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• On Dynamic DFS Tree in Directed Graphs

Cited in

(19)

• Output sensitive fault tolerant maximum matching
• Fault tolerant depth first search in undirected graphs: simple yet efficient
• Space-efficient fully dynamic DFS in undirected graphs
• Incremental algorithm for maintaining a DFS tree for undirected graphs
• 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
• Connectivity oracles for graphs subject to vertex failures
• Fault-tolerant subgraph for single-source reachability: general and optimal
• Fully dynamic maximal matching in O( n) update time (corrected version)
• Generic single edge fault tolerant exact distance oracle
• Depth First Search in the Semi-streaming Model
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
• An improved algorithm for incremental DFS tree in undirected graphs
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Sublinear-time reductions for big data computing
• How fast can we play Tetris greedily with rectangular pieces?
• Conditional lower bounds for dynamic geometric measure problems
• Conditional lower bounds for dynamic geometric measure problems

This page was built for publication: Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier

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