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

depth-first searchdirected graphdecrementaldynamic DFS tree

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1670815 (Why is no real title available?)
• 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 LCA Queries on Trees
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Fully-dynamic min-cut
• 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)

• scientific article; zbMATH DE number 7561709 (Why is no real title available?)
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs
• Incremental DFS algorithms: a theoretical and experimental study
• 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
• 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)
• 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)