Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier

Related Items

Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
The incremental maintenance of a depth-first-search tree in directed acyclic graphs
On dynamic shortest paths problems
$f$-sensitivity distance oracles and routing schemes
Fully-dynamic min-cut
Mantaining dynamic matrices for fully dynamic transitive closure
Depth-first search is inherently sequential
Fractional cascading. I: A data structuring technique
A random NC algorithm for depth first search
A topological approach to dynamic graph connectivity
Complexity models for incremental computation
Dynamically switching vertices in planar graphs
A data structure for dynamic trees
Fully dynamic biconnectivity in graphs
Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
Fault tolerant additive and $(\mu, \alpha)$-spanners
Faster randomized worst-case update time for dynamic subgraph connectivity
The phase transition in random graphs: A simple proof
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
On Dynamic DFS Tree in Directed Graphs
A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
Dynamic Connectivity: Connecting to Networks and Geometry
Parallel Depth-First Search in General Directed Graphs
Randomized fully dynamic graph algorithms with polylogarithmic time per operation
Fully dynamic randomized algorithms for graph spanners
Dynamic Subgraph Connectivity with Geometric Applications
Oracles for Distances Avoiding a Failed Node or Link
Improved Dynamic Reachability Algorithms for Directed Graphs
Worst-case update times for fully-dynamic all-pairs shortest paths
New Data Structures for Subgraph Connectivity
The Complexity of Satisfiability of Small Depth Circuits
Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
Parallel Algorithms for Depth-First Searches I. Planar Graphs
Finding Dominators in Directed Graphs
Efficient Planarity Testing
Sparsification—a technique for speeding up dynamic graph algorithms
Improved Data Structures for Fully Dynamic Biconnectivity
Dynamic DFS in Undirected Graphs: breaking the O(m) barrier
Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version)
Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n^{1/2 - ε})-time
Fully-dynamic minimum spanning forest with improved worst-case update time
Fully Dynamic Connectivity Oracles under General Vertex Updates
Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
Fault Tolerant Spanners for General Graphs
A new approach to dynamic all pairs shortest paths
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
Depth-First Search and Linear Graph Algorithms
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
Dynamic graph connectivity in polylogarithmic worst case time
Fully dynamic geometric spanners
On the complexity of $k$-SAT