Fully Dynamic Minimum Spanning Trees
- PDF / 232,123 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 78 Downloads / 275 Views
is especially important, as these graphs arise frequently in applications. Open Problems A number of problems related to the work of Eppstein et al. [2,3] remain open. First, can the running times per operation be improved? Second, as in the case of general graphs, also for planar graphs fully dynamic 2-edge connectivity can be solved in polylogarithmic time per update, while the best known update bounds for higher edge and vertex connectivity are polynomial: Can this gap be reduced, i. e., can one design polylogarithnmic algorithms at least for fully dynamic 3-edge and 3-vertex connectivity? Third, in the special case of planar graphs can one solve fully dynamic k-vertex connectivity for general k?
F
Problem Definition Let G = (V ; E) be an undirected weighted graph. The problem considered here is concerned with maintaining efficiently information about a minimum spanning tree of G (or minimum spanning forest if G is not connected), when G is subject to dynamic changes, such as edge insertions, edge deletions and edge weight updates. One expects from the dynamic algorithm to perform update operations faster than recomputing the entire minimum spanning tree from scratch. Throughout, an algorithm is said to be fully dynamic if it can handle both edge insertions and edge deletions. A partially dynamic algorithm can handle either edge insertions or edge deletions, but not both: it is incremental if it supports insertions only, and decremental if it supports deletions only.
Cross References Dynamic Trees Fully Dynamic All Pairs Shortest Paths Fully Dynamic Connectivity Fully Dynamic Higher Connectivity Fully Dynamic Minimum Spanning Trees Fully Dynamic Planarity Testing Fully Dynamic Transitive Closure Recommended Reading 1. Galil Z., Italiano G.F., Sarnak N.: Fully dynamic planarity testing with applications. J. ACM 48, 28–91 (1999) 2. Eppstein D., Galil Z., Italiano G.F., Spencer T.H.: Separator based sparsification I: planarity testing and minimum spanning trees. J. Comput. Syst. Sci., Special issue of STOC 93 52(1), 3–27 (1996) 3. Eppstein D., Galil Z., Italiano G.F., Spencer T.H.: Separator based sparsification II: edge and vertex connectivity. SIAM J. Comput. 28, 341–381 (1999) 4. Giammarresi D., Italiano G.F.: Decremental 2- and 3-connectivity on planar graphs. Algorithmica 16(3), 263–287 (1996) 5. Hershberger J., M.R., Suri S.: Data structures for two-edge connectivity in planar graphs. Theor. Comput. Sci. 130(1), 139–161 (1994)
Fully Dynamic Minimum Spanning Trees 2000; Holm, de Lichtenberg, Thorup GIUSEPPE F. ITALIANO Department of Information and Computer Systems, University of Rome, Rome, Italy Keywords and Synonyms Dynamic minimum spanning forests
Key Results The dynamic minimum spanning forest algorithm presented in this section builds upon the dynamic connectivity algorithm described in the entry “Fully Dynamic Connectivity”. In particular, a few simple changes to that algorithm are sufficient to maintain a minimum spanning forest of a weighted undirected graph upon deletions of edges [13]
Data Loading...
