Randomized fully dynamic graph algorithms with polylogarithmic time per operation
Henzinger, Monika H
King, Valerie
This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor.
Let n denote the number of nodes in the graph. For a sequence of Ω(m0) operations, where m0 is the number of edges in the initial graph, the expected time for p updates is O(p log3 n) (througout the paper the logarithms are based 2) for connectivity and bipartiteness. The worst-case time for one query is O(log n/log log n). For the k-edge witness problem (“Does the removal of k given edges disconnect the graph?”) the expected time for p updates is O(p log3 n) and the expected time for q queries is O(qk log3 n). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O(pk log3 n). This implies an algorithm to maintain a 1 + ε-approximation of the minimum spanning tree in expected time O((p log3 n logU)/ε) for p updates, where the weights of the edges are between 1 and U.
Association for Computing Machinery
1999
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/11769
Henzinger M, King V. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. <i>Journal of the ACM</i>. 1999;46(4):502-516. doi:<a href="https://doi.org/10.1145/320211.320215">10.1145/320211.320215</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1145/320211.320215
info:eu-repo/semantics/altIdentifier/issn/0004-5411
info:eu-repo/semantics/altIdentifier/issn/1557-735X
info:eu-repo/semantics/closedAccess