Maintenance of a minimum spanning forest in a dynamic plane graph
From MaRDI portal
Publication:3990614
DOI10.1016/0196-6774(92)90004-VzbMath0751.05081WikidataQ61609652 ScholiaQ61609652MaRDI QIDQ3990614
Roberto Tamassia, David Eppstein, Giuseppe F. Italiano, Mordechai M. Yung, Jeffery Westbrook, Robert Endre Tarjan
Publication date: 28 June 1992
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(92)90004-v
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Maintaining spanning trees of small diameter, The Painter’s Problem: Covering a Grid with Colored Connected Polygons, A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING, Unnamed Item, Dynamic 2- and 3-connectivity on planar graphs, Lower bounds for dynamic algorithms, Decremental SPQR-trees for Planar Graphs, Efficient Extraction of Multiple Kuratowski Subdivisions, FINDING PLANAR REGIONS IN A TERRAIN – IN PRACTICE AND WITH A GUARANTEE, Minimum-weight spanning tree algorithms. A survey and empirical study, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., A uniform self-stabilizing minimum diameter spanning tree algorithm, Fully Dynamic Transitive Closure in plane dags with one source and one sink, Dynamic connectivity in disk graphs, On-line convex planarity testing, Dynamic connectivity in digital images, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Efficient authenticated data structures for graph connectivity and geometric search problems, Planar and grid graph reachability problems, Efficient algorithms for computing Reeb graphs, Maintaining dynamic minimum spanning trees: an experimental study, A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs, Dynamic expression trees, Optimal decremental connectivity in planar graphs, Dynamic planar embeddings of dynamic graphs, Incremental convex planarity testing, Decremental 2- and 3-connectivity on planar graphs, Constant-time dynamic weight approximation for minimum spanning forest, Single-source shortest paths and strong connectivity in dynamic planar graphs, Competitive graph searches, Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning, Dynamic Trees and Dynamic Point Location