The minimum spanning tree problem on a planar graph (Q1805468)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The minimum spanning tree problem on a planar graph |
scientific article; zbMATH DE number 756168
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The minimum spanning tree problem on a planar graph |
scientific article; zbMATH DE number 756168 |
Statements
The minimum spanning tree problem on a planar graph (English)
0 references
14 June 1995
0 references
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.
0 references
graphical algorithms
0 references
minimum weight spanning tree
0 references
planar graphs
0 references
time complexity
0 references
spanning tree
0 references
0 references
