David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert E. Tarjan, Jeffery Westbrook, Moti Yung  Home/Search
Context Related
| yale.edu/WWW/users...ic_planar_mst.ps.Z Cached: PS.gz PS PDF DjVu Image Update Help From: uci.edu/~eppstein/pub...graphdyn (more) Homepages: D.Eppstein G.Italiano R.Tamassia R.Tarjan J.Westbrook [2] M.Yung [2] HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: We give an efficient algorithm for maintaining a minimum spanning forest of a plane graph subject to on-line modifications. The modifications supported include changes in the edge weights, and insertion and deletion of edges and vertices which are consistent with the given embedding. Our algorithm runs in O(log n) time per operation and O(n) space. (Update)
Context of citations to this paper: More
.... runs in time O(n k 2 log 2 n) Recently, Frederickson s technique for maintaining a MST in a dynamic planar graph has been improved [12, 17], leading to a bound for the k best spanning trees problem of O(n k 2 log n) this improves the bound of [18] whenever k = O(n log n)...
...after each insertion operation. Previous work on dynamic planarity testing and dynamic graph drawing is reported in [3, 4, 11, 12, 13, 14, 17, 18, 25, 40]. Besides their theoretical significance, our results are motivated by the development of advanced graph drawing systems....
Cited by: More
Authenticated Data Structures for Graph and Geometric .. - Goodrich, Tamassia.. (2001) (Correct)
On-Line Convex Planarity Testing - Di Battista, Tamassia, Vismara (1995) (Correct)
Randomized Dynamic Graph ALgorithms with Polylogarithmic Time .. - Henzinger, King (1995) (Correct)
Active bibliography (related documents): More All
1.3: Maintaining Biconnected Components of Dynamic Planar Graphs - Galil, Italiano (1991) (Correct)
1.0: Combine and Conquer - Cohen (1992) (Correct)
0.9: Lower And Upper Bounds For Incremental Algorithms - Berman (1992) (Correct)
Similar documents based on text: More All
0.5: Fully Dynamic Planarity Testing with Applications - Galil, Italiano, Sarnak (Correct)
0.3: Fully Dynamic Algorithms for Edge Connectivity Problems - Galil, Italiano (1991) (Correct)
0.2: Fast Incremental Planarity Testing - Westbrook (1992) (Correct)
Related documents from co-citation: More All
26: A Data Structure for Dynamic Trees (context) - Sleator, Tarjan - 1983
25: Data structures for on-line updating of minimum spanning trees (context) - Frederickson - 1985
19: Sparsification --- A Technique for Speeding up Dynamic Algorithms (context) - Eppstein, Galil et al. - 1996
BibTeX entry: (Update)
D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, and M. Yung, Maintenance of a minimum spanning forest in a dynamic planar graph, J. Algorithms, 13 (1992), pp. 33--54. http://citeseer.nj.nec.com/eppstein92maintenance.html More
@inproceedings{ eppstein90maintenance,
author = "David Eppstein and Giuseppe F. Italiano and Roberto Tamassia and Robert Endre Tarjan and Jeffery Westbrook and Moti Yung",
title = "Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph",
booktitle = "Symposium on Discrete Algorithms",
pages = "1-11",
year = "1990",
url = "citeseer.nj.nec.com/eppstein92maintenance.html" }
Citations (may not include all citations):381 Graph Theory (context) - Harary - 1972
223 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
155 A data structure for dynamic trees (context) - Sleator, Tarjan - 1983
151 Self-adjusting binary search trees (context) - Sleator, Tarjan - 1985
130 Society for Industrial and Applied Mathematics (context) - Tarjan, Network - 1983
112 Efficient planarity testing (context) - Hopcroft, Tarjan - 1974
104 Data structures for on-line updating of minimum spanning tre.. (context) - Frederickson - 1985
92 and graph planarity using PQ-tree algorithms (context) - Booth, Lueker et al. - 1976
71 Amortized computational complexity (context) - Tarjan - 1985
53 A linear algorithm for embedding planar graphs using PQ-tree.. (context) - Chiba, Nishizeki et al. - 1985
41 line edge deletion problem (context) - Even, Shiloach - 1981
37 Incremental algorithms for minimal length paths (context) - Ausiello, Italiano et al. - 1990
37 Finding minimum spanning trees (context) - Cheriton, Tarjan - 1976
33 Graph Theory (context) - Tutte - 1984
30 Incremental planarity testing (context) - Battista, Tamassia - 1989
26 On finding and updating spanning trees and shortest paths (context) - Spira, Pan - 1975
25 Finding paths and deleting edges in directed acyclic graphs (context) - Italiano - 1988
25 Updating distances in dynamic graphs (context) - Even, Gazit - 1985
24 Amortized efficiency of a path retrieval data structure (context) - Italiano - 1986
23 line computation of transitive closure for graphs (context) - Ibaraki, Katoh - 1983
21 Maintenance of transitive closure and transitive reduction o.. - Poutr'e, van Leeuwen - 1988
18 A dynamic data structure for planar graph embedding (context) - Tamassia - 1988
17 Sensitivity analysis of minimum spanning trees and shortest .. (context) - Tarjan - 1982
13 A dynamization of the all pairs least cost path problem (context) - Rohnert - 1985
13 Algorithms for updating minimum spanning trees (context) - Chin, Houck - 1978
12 A topological approach to dynamic graph connectivity (context) - Reif - 1987
11 Efficient algorithms for graphic matroid intersection and pa.. (context) - Gabow, Stallmann - 1985
6 Fully dynamic techniques for point location and transitive c.. (context) - Preparata, Tamassia - 1988
5 Use of dynamic trees in a network simplex algorithm for the .. (context) - Goldberg, Grigoriadis et al.
5 Dynamic data structures for series parallel digraphs (context) - Italiano, Spaccamela et al. - 1989
4 A dynamic transitive closure algorithm (context) - Yellin - 1988
4 line maintenance of the connected components of dynamic grap.. (context) - Harel - 1982
1 Department of Computer Science (context) - Battista, Tamassia et al. - 1989
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.ics.uci.edu/~eppstein/pubs/graph-dyn.html):
Dynamic Connectivity in Digital Images - Eppstein (1996) (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute