Dynamic graph connectivity in polylogarithmic worst case time

DOI10.1137/1.9781611973105.81zbMath1423.68345OpenAlexW4238411931WikidataQ56659733 ScholiaQ56659733MaRDI QIDQ5741790

Ben Mountjoy, Bruce M. Kapron, Valerie King

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/d3b93729d50038a868d6dde1ac32f919168877fa

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Connectivity (05C40)

Related Items (28)

Sketching and Embedding are Equivalent for Norms ⋮ Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8 ⋮ Incremental algorithm for maintaining a DFS tree for undirected graphs ⋮ Deterministic dynamic matching in worst-case update time ⋮ Optimal decremental connectivity in planar graphs ⋮ Dynamic connectivity in disk graphs ⋮ Unnamed Item ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Labeled graph sketches: keeping up with real-time graph streams ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dynamic graph coloring ⋮ A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Unnamed Item ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Unnamed Item ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time ⋮ Fully Dynamic Connectivity Oracles under General Vertex Updates ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time

This page was built for publication: Dynamic graph connectivity in polylogarithmic worst case time