On Dynamic DFS Tree in Directed Graphs
From MaRDI portal
Publication:2946380
DOI10.1007/978-3-662-48054-0_9zbMath1465.68055OpenAlexW1523934134MaRDI QIDQ2946380
Surender Baswana, Keerti Choudhary
Publication date: 16 September 2015
Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-48054-0_9
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Directed graphs (digraphs), tournaments (05C20) Randomized algorithms (68W20)
Related Items (8)
Fault tolerant depth first search in undirected graphs: simple yet efficient ⋮ Incremental algorithm for maintaining a DFS tree for undirected graphs ⋮ A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs ⋮ Unnamed Item ⋮ Randomization for Efficient Dynamic Graph Algorithms ⋮ Unnamed Item ⋮ Space-efficient fully dynamic DFS in undirected graphs ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier
Cites Work
- Unnamed Item
- The incremental maintenance of a depth-first-search tree in directed acyclic graphs
- Fully-dynamic min-cut
- Depth-first search is inherently sequential
- A topological approach to dynamic graph connectivity
- Complexity models for incremental computation
- Semi-dynamic breadth-first search in digraphs
- Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
- Dynamic LCA Queries on Trees
- Multiplying matrices faster than coppersmith-winograd
- A new approach to dynamic all pairs shortest paths
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Algorithms – ESA 2004
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: On Dynamic DFS Tree in Directed Graphs
