The minimum spanning tree problem on a planar graph

DOI10.1016/0166-218X(94)00095-UMaRDI QIDQ1805468zbMATH OpenFDO

Authors Tomomi Matsui

Publication date 14 June 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(94)00095-U

zbMATH Keywords

graphical algorithmsminimum weight spanning treeplanar graphsspanning treetime complexity

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

A minimum weight spanning tree algorithm for planar graphs with time complexity \(O(n)\) is given. The algorithm maintains a pair of a planar graph and its dual graph and breeds both a minimum spanning tree for the original graph and a maximum spanning tree of its dual. The author claims that his algorithm is easy to implement compared to other existing algorithms for the problem which have the same time complexity.

Recommendations

• An optimal parallel algorithm for minimum spanning trees in planar graphs
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Two linear time algorithms for MST on minor closed graph classes.
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• An optimal minimum spanning tree algorithm

Cites work

• A note on two problems in connexion with graphs
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Efficient Planarity Testing
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding Minimum Spanning Trees
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• On the shortest spanning subtree of a graph and the traveling salesman problem

Cited in

(11)

• Planar bichromatic minimum spanning trees
• An O(N log N) minimal spanning tree algorithm for N points in the plane
• Faster shortest paths in dense distance graphs, with applications
• Efficient minimum spanning tree construction with Delaynay triangulation
• Minimum spanning tree cycle intersection problem
• An algorithm for \(k^{\text{th}}\) minimum spanning tree
• Two linear time algorithms for MST on minor closed graph classes.
• The saga of minimum spanning trees
• A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
• scientific article; zbMATH DE number 1910742 (Why is no real title available?)
• Contracting a planar graph efficiently

This page was built for publication: The minimum spanning tree problem on a planar graph

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