An improved algorithm for incremental DFS tree in undirected graphs

DOI10.4230/LIPICS.SWAT.2018.16MaRDI QIDQ5116480zbMATH OpenFDO

Authors Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang

Publication date 25 August 2020

Full work available at URL https://arxiv.org/abs/1607.04913

zbMATH Keywords

fractional cascadingfully dynamic algorithmDFS tree

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
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Incremental DFS algorithms: a theoretical and experimental study
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Incremental algorithm for maintaining a DFS tree for undirected graphs

Cites work

• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• A new approach to dynamic all pairs shortest paths
• Depth-First Search and Linear Graph Algorithms
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Dynamic graph connectivity in polylogarithmic worst case time
• Fractional cascading. I: A data structuring technique
• Fractional cascading. II: Applications
• Fully Dynamic Maximal Matching in O (log n) Update Time
• 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
• Sorted range reporting
• Sparsification—a technique for speeding up dynamic graph algorithms
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs

Cited in

(13)

• 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
• 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
• Sublinear-time reductions for big data computing
• Sublinear-time reductions for big data computing
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Connectivity oracles for graphs subject to vertex failures

This page was built for publication: An improved algorithm for incremental DFS tree in undirected graphs

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