Randomized fully dynamic graph algorithms with polylogarithmic time per operation

DOI10.1145/320211.320215zbMath1065.68665OpenAlexW1992869351MaRDI QIDQ3158547

Valerie King, Monika R. Henzinger

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://infoscience.epfl.ch/record/99353

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Randomized algorithms (68W20)

Related Items (32)

A Planar linear arboricity conjecture ⋮ Upper and lower bounds for fully retroactive graph problems ⋮ Faster Fully-Dynamic Minimum Spanning Forest ⋮ Fully dynamic biconnectivity in graphs ⋮ A survey on combinatorial optimization in dynamic environments ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ Incremental algorithm for maintaining a DFS tree for undirected graphs ⋮ Kinetic Geodesic Voronoi Diagrams in a Simple Polygon ⋮ Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay ⋮ Optimal decremental connectivity in planar graphs ⋮ Unnamed Item ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ The saga of minimum spanning trees ⋮ LS(graph): a constraint-based local search for constraint optimization on trees and paths ⋮ Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete ⋮ A consistent semantics of self-adjusting computation ⋮ Discovering recurring activity in temporal networks ⋮ Maintaining dynamic minimum spanning trees: an experimental study ⋮ Dynamic Approximate Vertex Cover and Maximum Matching ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ Unnamed Item ⋮ Randomization for Efficient Dynamic Graph Algorithms ⋮ Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning ⋮ Empire of colonies: Self-stabilizing and self-organizing distributed algorithm ⋮ Unnamed Item ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Dynamic connectivity for axis-parallel rectangles ⋮ Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Time Windowed Data Structures for Graphs ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time ⋮ Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks

This page was built for publication: Randomized fully dynamic graph algorithms with polylogarithmic time per operation