Dynamic graph connectivity in polylogarithmic worst case time
From MaRDI portal
Recommendations
- Lower bounds for fully dynamic connectivity problems in graphs
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Near-optimal fully-dynamic graph connectivity
- Faster worst case deterministic dynamic connectivity
- Faster deterministic fully-dynamic graph connectivity
- scientific article; zbMATH DE number 1263228
- Faster randomized worst-case update time for dynamic subgraph connectivity
- On the computational complexity of dynamic graph problems
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
Cited in
(56)- On certificates and lookahead in dynamic graph problems
- Optimal decremental connectivity in planar graphs
- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
- Constant-time dynamic weight approximation for minimum spanning forest
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Labeled graph sketches: keeping up with real-time graph streams
- Optimal offline dynamic 2, 3-edge/vertex connectivity
- Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study
- Faster randomized worst-case update time for dynamic subgraph connectivity
- Incremental algorithm for maintaining a DFS tree for undirected graphs
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- Connectivity oracles for graphs subject to vertex failures
- Dynamic Subgraph Connectivity with Geometric Applications
- New data structures for subgraph connectivity
- \texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)
- Sketching and embedding are equivalent for norms
- Incremental and fully dynamic subgraph connectivity for emergency planning
- Faster worst case deterministic dynamic connectivity
- Inverse reinforcement learning via nonparametric spatio-temporal subgoal modeling
- Deterministic Edge Connectivity in Near-Linear Time
- Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
- Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
- Decremental SPQR-trees for Planar Graphs
- Decremental strongly connected components and single-source reachability in near-linear time
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model
- Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
- An improved algorithm for incremental DFS tree in undirected graphs
- Fully dynamic connectivity oracles under general vertex updates
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Fully dynamic maximal matching in O( n) update time
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Dynamic graph coloring
- Deterministic dynamic matching in worst-case update time
- Dynamic connectivity in disk graphs
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- Fast algorithms via dynamic-oracle matroids
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Near-optimal distributed computation of small vertex cuts
- Move schedules: fast persistence computations in coarse dynamic settings
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- An efficient strongly connected components algorithm in the fault tolerant model
- Fully dynamic sequential and distributed algorithms for MAX-CUT
- On the complexity of algorithms with predictions for dynamic graph problems
- Deterministic fault-tolerant connectivity labeling scheme
- Learning spanning forests optimally in weighted undirected graphs with CUT queries
- A generalized matching reconfiguration problem
- Good r-divisions imply optimal amortized decremental biconnectivity
- Fully-adaptive dynamic connectivity of square intersection graphs
- The structure of minimum vertex cuts
- Connectivity oracles for predictable vertex failures
- Tree-packing revisited: faster fully dynamic min-cut and arboricity
- Fault-tolerant labeling and compact routing schemes
- Efficient contractions of dynamic graphs -- with applications
- Dynamic algorithms for submodular matching
- Adjacency queries in dynamic sparse graphs
This page was built for publication: Dynamic graph connectivity in polylogarithmic worst case time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741790)
