On Dynamic DFS Tree in Directed Graphs

DOI10.1007/978-3-662-48054-0_9MaRDI QIDQ2946380zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

decrementaldepth-first searchdirected graphdynamic DFS tree

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• On the treewidth of dynamic graphs
• On the treewidth of dynamic graphs
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Space-efficient fully dynamic DFS in undirected graphs
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• Dynamic algorithms for graphs of bounded treewidth
• Dynamic algorithms for graphs of bounded treewidth
• Incremental algorithm for maintaining a DFS tree for undirected graphs
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient

Cites work

• A new approach to dynamic all pairs shortest paths
• A topological approach to dynamic graph connectivity
• Algorithms – ESA 2004
• Complexity models for incremental computation
• Depth-First Search and Linear Graph Algorithms
• Depth-first search is inherently sequential
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Dynamic LCA Queries on Trees
• Fully-dynamic min-cut
• scientific article; zbMATH DE number 1670815 (Why is no real title available?)
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• Multiplying matrices faster than coppersmith-winograd
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Semi-dynamic breadth-first search in digraphs
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs

Cited in

(12)

• 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
• Randomization for efficient dynamic graph algorithms (invited talk)
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Incremental DFS algorithms: a theoretical and experimental study
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
• An improved algorithm for incremental DFS tree in undirected graphs
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier

This page was built for publication: On Dynamic DFS Tree in Directed Graphs

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