Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time

DOI10.1145/3055399.3055447zbMath1370.68234arXiv1611.03745OpenAlexW2571471359MaRDI QIDQ4978052

Danupon Nanongkai, Thatchaphol Saranurak

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.03745

zbMATH Keywords

graph decompositionsparse recoverydynamic spanning forestlocal graph partitioning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (7)

Faster connectivity in low-rank hypergraphs via expander decomposition ⋮ Deterministic dynamic matching in worst-case update time ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier

This page was built for publication: Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n^{1/2 - ε})-time