Incremental algorithm for maintaining a DFS tree for undirected graphs

DOI10.1007/S00453-016-0204-1MaRDI QIDQ2408922zbMATH OpenOpenAlexFDO

Authors Surender Baswana, Shahbaz Khan

Publication date 10 October 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-016-0204-1

zbMATH Keywords

dynamicundirected graphdepth first searchincremental

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1670815 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 5764857 (Why is no real title available?)
• A new approach to dynamic all pairs shortest paths
• A topological approach to dynamic graph connectivity
• Complexity models for incremental computation
• Depth-First Search and Linear Graph Algorithms
• Depth-first search is inherently sequential
• Dynamic LCA Queries on Trees
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Dynamic graph connectivity in polylogarithmic worst case time
• Fully dynamic geometric spanners
• Fully dynamic randomized algorithms for graph spanners
• Fully-dynamic min-cut
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• On Dynamic DFS Tree in Directed Graphs
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Sparsification—a technique for speeding up dynamic graph algorithms
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs
• The phase transition in random graphs: a simple proof

Cited in

(5)

• Depth First Search in the Semi-streaming Model
• An improved algorithm for incremental DFS tree in undirected graphs
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• Fault tolerant depth first search in undirected graphs: simple yet efficient
• On Dynamic DFS Tree in Directed Graphs

This page was built for publication: Incremental algorithm for maintaining a DFS tree for undirected graphs

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