Incremental algorithm for maintaining a DFS tree for undirected graphs
From MaRDI portal
Publication:2408922
DOI10.1007/S00453-016-0204-1zbMATH Open1372.68200OpenAlexW2512395816MaRDI QIDQ2408922FDOQ2408922
Shahbaz Khan, Surender Baswana
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
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Cites Work
- Title not available (Why is that?)
- Depth-First Search and Linear Graph Algorithms
- Title not available (Why is that?)
- A new approach to dynamic all pairs shortest paths
- Depth-first search is inherently sequential
- A topological approach to dynamic graph connectivity
- The incremental maintenance of a depth-first-search tree in directed acyclic graphs
- Fully dynamic randomized algorithms for graph spanners
- Title not available (Why is that?)
- Sparsification—a technique for speeding up dynamic graph algorithms
- Dynamic LCA Queries on Trees
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- The phase transition in random graphs: a simple proof
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Complexity models for incremental computation
- Dynamic approximate all-pairs shortest paths in undirected graphs
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Dynamic graph connectivity in polylogarithmic worst case time
- Fully-dynamic min-cut
- On Dynamic DFS Tree in Directed Graphs
- Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
- Fully dynamic geometric spanners
Cited In (4)
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)
