Maintenance of a minimum spanning forest in a dynamic plane graph

DOI10.1016/0196-6774(92)90004-VMaRDI QIDQ3990614zbMATH OpenOpenAlexDBLPWikidataFDO

Authors David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert E. Tarjan, Jeffery R. Westbrook, Moti Yung

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

dynamic treesminimum spanning forestplane graphs

Mathematics Subject Classification ID

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

Recommendations

• Maintaining minimum spanning forests in dynamic graphs
• Maintaining minimum spanning trees in dynamic graphs
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Separator based sparsification. I: Planarity testing and minimum spanning trees
• scientific article; zbMATH DE number 176746

Cited in

(53)

• 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
• Nearly linear time minimum spanning tree maintenance for transient node failures
• Separator based sparsification. I: Planarity testing and minimum spanning trees
• 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
• scientific article; zbMATH DE number 1617247 (Why is no real title available?)
• Maintaining minimum spanning forests in dynamic graphs
• Dynamic connectivity in digital images
• Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs
• Maintaining Nets and Net Trees under Incremental Motion
• scientific article; zbMATH DE number 177564 (Why is no real title available?)
• Dynamic Trees and Dynamic Point Location
• scientific article; zbMATH DE number 1256643 (Why is no real title available?)
• scientific article; zbMATH DE number 1003237 (Why is no real title available?)
• Maintaining minimum spanning trees in dynamic graphs
• Maintenance of a Spanning Tree For Dynamic Graphs by Mobile Agents and Local Computations
• The painter's problem: covering a grid with colored connected polygons
• Maintaining spanning trees of small diameter
• A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING
• scientific article; zbMATH DE number 1926664 (Why is no real title available?)
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Maintaining centdians in a fully dynamic forest with top trees
• Decremental SPQR-trees for Planar Graphs
• Dynamic 2- and 3-connectivity on planar graphs
• Lower bounds for dynamic algorithms
• scientific article; zbMATH DE number 7238975 (Why is no real title available?)
• Multi-period maintenance scheduling of tree networks with minimum flow disruption
• Competitive Maintenance of Minimum Spanning Trees in Dynamic Graphs
• Efficient Extraction of Multiple Kuratowski Subdivisions
• Efficient authenticated data structures for graph connectivity and geometric search problems
• FINDING PLANAR REGIONS IN A TERRAIN – IN PRACTICE AND WITH A GUARANTEE
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Minimum-weight spanning tree algorithms. A survey and empirical study
• 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
• Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
• Dynamic maintenance of shortest path trees in simple polygons
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• On partitioning minimum spanning trees
• Good r-divisions imply optimal amortized decremental biconnectivity
• Planar and grid graph reachability problems
• Dynamic maintenance of planar digraphs, with applications
• Efficient algorithms for computing Reeb graphs
• Maintaining dynamic minimum spanning trees: an experimental study

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3990614)