An Improved Algorithm for Incremental DFS Tree in Undirected Graphs

No abstract is available for this paper.

• Publication year

  2016

• Venue

  Scandinavian Workshop on Algorithm Theory

• Publication date

  2016-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.SWAT.2018.16
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs

  2017influential reference
• Improved Distance Sensitivity Oracles via Tree Partitioning

  2016influential reference
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching

  2016cited by this paper
• Dynamic DFS in Undirected Graphs: breaking the O(m) barrier

  2015influential reference
• On Dynamic DFS Tree in Directed Graphs

  2015influential reference
• Incremental Algorithm for Maintaining a DFS Tree for Undirected Graphs

  2014cited by this paper
• Dynamic graph connectivity in polylogarithmic worst case time

  2013cited by this paper
• Sorted Range Reporting

  2012cited by this paper
• Fully Dynamic Maximal Matching in O (log n) Update Time

  2011cited by this paper
• Dynamic approximate all-pairs shortest paths in undirected graphs

  2004cited by this paper
• A new approach to dynamic all pairs shortest paths

  2004cited by this paper
• Dynamic Transitive Closure via Dynamic Matrix Inverse

  2004cited by this paper
• Improved dynamic reachability algorithms for directed graphs

  2002cited by this paper
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

  2001cited by this paper
• Fully-dynamic min-cut

  2001cited by this paper
• The LCA Problem Revisited

  2000cited by this paper
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation

  1999cited by this paper
• The Incremental Maintenance of a Depth-First-Search Tree in Directed Acyclic Graphs

  1997cited by this paper
• Sparsification-a technique for speeding up dynamic graph algorithms

  1992cited by this paper
• Fractional cascading: II. Applications

  1986cited by this paper
• Fractional cascading: I. A data structuring technique

  1986cited by this paper
• Depth-First Search and Linear Graph Algorithms

  1972cited by this paper

• The Quest for Efficient Search Algorithms: Uninformed vs Informed Approaches

  2024cites this paper
• Tight dynamic problem lower bounds from generalized BMM and OMv

  2022cites this paper
• Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)

  2022cites this paper
• Fault Tolerant Depth First Search in Undirected Graphs: Simple Yet Efficient

  2022cites this paper
• Sublinear-time Reductions for Big Data Computing

  2021cites this paper
• Fully Dynamic Depth-First Search in Directed Graphs

  2019cites this paper
• Space-Efficient Fully Dynamic DFS in Undirected Graphs

  2019influential citation
• Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient

  2018cites this paper
• Dynamic DFS in Undirected Graphs: breaking the O(m) barrier

  2015cites this paper