This paper gives a new deterministic algorithm for the dynamic Minimum Spanning Forest (MSF) problem in the EREW PRAM model, where the goal is to maintain a MSF of a weighted graph with n vertices and m edges while supporting edge insertions and deletions. We show that one can solve the dynamic MSF problem using @math processors and @math worst-case update time, for a total of @math work. This improves on the work of Ferragina [IPPS 1995] which costs @math worst-case update time and @math work.
In the sequential setting, the fastest deterministic worst-case algorithm for dynamic MSF has an @math worst-case update time @cite_22 @cite_3 . Henzinger and King @cite_9 showed a deterministic algorithm for dynamic MSF with amortized update time of @math . @cite_18 designed another deterministic algorithm which has an amortized update time of @math , and later @cite_1 improved the amortized update time to @math . When allowing randomization, Wulff-Nilsen @cite_4 gave a randomized Las-Vegas algorithm for dynamic MSF with an expected worst-case update time of @math for some constant @math , and @cite_13 gave a randomized Las-Vegas algorithm with an expected worst-case update time of @math . et al @cite_5 proved a lower bound of @math update time for dynamic connectivity, which is also a lower bound for dynamic MSF.
@cite_18 @cite_4 @cite_22 @cite_9 @cite_1 @cite_3 @cite_5 @cite_13
2045430818 2565540516 2121473031 2128744826 2133521834 144796997 1963524245 2964264613
Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O(log2 n) for connectivity, O(log4 n) for minimum spanning forest, 2-edge connectivity, and O(log5 n) biconnectivity. We give a Las Vegas data structure which maintains a minimum spanning forest in an n-vertex edge-weighted undirected dynamic graph undergoing updates consisting of any mixture of edge insertions and deletions. Each update is supported in O(n1 2 - c) worst-case time w.h.p. where c > 0 is some constant, and this bound also holds in expectation. This is the first data structure achieving an improvement over the O(√n) deterministic worst-case update time of , a bound that has been standing for 25 years. In fact, it was previously not even known how to maintain a spanning forest of an unweighted graph in worst-case time polynomially faster than Θ(√n). Our result is achieved by first giving a reduction from fully-dynamic to decremental minimum spanning forest preserving worst-case update time up to logarithmic factors. Then decremental minimum spanning forest is solved using several novel techniques, one of which involves keeping track of low-conductance cuts in a dynamic graph. An immediate corollary of our result is the first Las Vegas data structure for fully-dynamic connectivity where each update is handled in worst-case time polynomially faster than Θ(√n) w.h.p.; this data structure has O(1) worst-case query time. Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph. For the case of a general graph, maintaining the data structure and updating the tree are shown to take @math time, where m is the number of edges in the graph. For the case of a planar graph, a data structure is presented which supports an update time of @math . These structures contribute to improved solutions for the on-line connected components problem and the problem of generating the K smallest spanning trees. We present the first fully dynamic algorithm for maintaining a minimum spanning tree in time o(√n) per operation. To be precise, the algorithm uses O(n 1 3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and, bipartiteness in amortized time O(n 1 3 log n) per update, with O(1) worst case time per query. We give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in O(log4n loglogn) expected amortized time per operation, improving the O(log4n) amortized bound of (STOC ’98, JACM ’01). We also provide a deterministic data structure with amortized update time O(log4n logloglogn loglogn). We assume the Word-RAM model with standard instructions. We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This technique enables us to prove an amortized randomized @math lower bound per operation for several data structural problems on @math elements, including partial sums, dynamic connectivity among disjoint paths (or a forest or a graph), and several other dynamic graph problems (by simple reductions). Such a lower bound breaks a long-standing barrier of @math for any dynamic language membership problem. It also establishes the optimality of several existing data structures, such as Sleator and Tarjan's dynamic trees. We also prove the first @math lower bound in the external-memory model without assumptions on the data structure (such as the comparison model). Our lower bounds also give a query-update trade-off curve matched, e.g., by several data structures for dynamic connectivity in graphs. We also prove matching upper and lower bounds for partial sums when parameterized by the word size and the maximum additive change in an update. We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an n-node graph undergoing edge insertions and deletions. Our algorithm guarantees an O(n^ o(1) ) worst-case update time with high probability. This significantly improves the two recent Las Vegas algorithms by Wulff-Nilsen Wulff-Nilsen16a with update time O(n^ 0.5-&#x2265;ilon ) for some constant &#x2265;ilon 0 and, independently, by Nanongkai and Saranurak NanongkaiS16 with update time O(n^ 0.494 ) (the latter works only for maintaining a spanning forest).Our result is obtained by identifying the common framework that both two previous algorithms rely on, and then improve and combine the ideas from both works. There are two main algorithmic components of the framework that are newly improved and critical for obtaining our result. First, we improve the update time from O(n^ 0.5-&#x2265;ilon ) in Wulff-Nilsen16a to O(n^ o(1) ) for decrementally removing all low-conductance cuts in an expander undergoing edge deletions. Second, by revisiting the contraction technique by Henzinger and King HenzingerK97b and HolmLT01, we show a new approach for maintaining a minimum spanning forest in connected graphs with very few (at most (1+o(1))n) edges. This significantly improves the previous approach in Wulff-Nilsen16a, NanongkaiS16 which is based on Fredericksons 2-dimensional topology tree Frederickson85 and illustrates a new application to this old technique.