An improved algorithm for incremental DFS tree in undirected graphs
From MaRDI portal
Publication:5116480
DOI10.4230/LIPICS.SWAT.2018.16zbMATH Open1477.05178arXiv1607.04913MaRDI QIDQ5116480FDOQ5116480
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Cites Work
- Depth-First Search and Linear Graph Algorithms
- Title not available (Why is that?)
- A new approach to dynamic all pairs shortest paths
- The incremental maintenance of a depth-first-search tree in directed acyclic graphs
- Sorted Range Reporting
- Sparsification—a technique for speeding up dynamic graph algorithms
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Fractional cascading. I: A data structuring technique
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Fractional cascading. II: Applications
- 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
- Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
- Fully Dynamic Maximal Matching in O (log n) Update Time
- Dynamic DFS in Undirected Graphs: breaking the O(m) barrier
- On Dynamic DFS Tree in Directed Graphs
- A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
- Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
Cited In (9)
- Title not available (Why is that?)
- A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
- Connectivity Oracles for Graphs Subject to Vertex Failures
- 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
- Sublinear-time reductions for big data computing
- Sublinear-time reductions for big data computing
- Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier
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)
