Maintenance of a minimum spanning forest in a dynamic plane graph

DOI10.1016/0196-6774(92)90004-VzbMath0751.05081OpenAlexW2094632707WikidataQ61609652 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

zbMATH Keywords

plane graphsminimum spanning forestdynamic trees

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (32)

Maintaining spanning trees of small diameter ⋮ Dynamic connectivity in digital images ⋮ Dynamic expression trees ⋮ Dynamic 2- and 3-connectivity on planar graphs ⋮ Lower bounds for dynamic algorithms ⋮ Decremental 2- and 3-connectivity on planar graphs ⋮ A uniform self-stabilizing minimum diameter spanning tree algorithm ⋮ Fully Dynamic Transitive Closure in plane dags with one source and one sink ⋮ Optimal decremental connectivity in planar graphs ⋮ Dynamic planar embeddings of dynamic graphs ⋮ Dynamic connectivity in disk graphs ⋮ On-line convex planarity testing ⋮ Efficient algorithms for computing Reeb graphs ⋮ The Painter’s Problem: Covering a Grid with Colored Connected Polygons ⋮ FINDING PLANAR REGIONS IN A TERRAIN – IN PRACTICE AND WITH A GUARANTEE ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Competitive graph searches ⋮ Maintaining dynamic minimum spanning trees: an experimental study ⋮ Efficient authenticated data structures for graph connectivity and geometric search problems ⋮ A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING ⋮ Minimum-weight spanning tree algorithms. A survey and empirical study ⋮ Efficient Extraction of Multiple Kuratowski Subdivisions ⋮ Planar and grid graph reachability problems ⋮ Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning ⋮ Unnamed Item ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Dynamic Trees and Dynamic Point Location ⋮ Incremental convex planarity testing ⋮ A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs

This page was built for publication: Maintenance of a minimum spanning forest in a dynamic plane graph