Computing Euclidean maximum spanning trees

DOI10.1007/BF01840396MaRDI QIDQ911288zbMATH OpenFDO

Authors Michael S. Paterson, Subhash Suri, Clyde l. Monma, Frances F. Yao

Publication date 1990

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01840396

zbMATH Keywords

clustersdiameter-partitioningfurthest-neighbor graphspanning trees

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Maximum spanning trees in normed planes
• Euclidean minimum spanning trees and bichromatic closest pairs
• Minimum spanning trees in d dimensions
• An algorithm for geometric minimum spanning trees requiring nearly linear expected time
• scientific article; zbMATH DE number 177542

Cites work

• Diameter partitioning
• Geometric applications of a matrix-searching algorithm
• Hierarchical clustering schemes
• How to search in history
• scientific article; zbMATH DE number 3945378 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3448387 (Why is no real title available?)
• scientific article; zbMATH DE number 867650 (Why is no real title available?)
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On the History of the Minimum Spanning Tree Problem
• The NP-completeness column: An ongoing guide
• The Ultimate Planar Convex Hull Algorithm?

Cited in

(22)

• A simple linear-time algorithm for computing the ring and MST of unimodal polygons
• Euclidean minimum spanning trees and bichromatic closest pairs
• How to find Steiner minimal trees in Euclidean \(d\)-space
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions
• Transitions in geometric minimum spanning trees
• An O(m n) algorithm for the max+sum spanning tree problem
• On minimum and maximum spanning trees of linearly moving points
• Short trees in polygons
• Geometric clustering in normed planes
• Spanning trees in multipartite geometric graphs
• An algorithm for geometric minimum spanning trees requiring nearly linear expected time
• Average case analysis of dynamic geometric optimization
• Equispreading tree in Manhattan distance
• Maximum spanning trees in normed planes
• Computing hierarchies of clusters from the Euclidean minimum spanning tree in linear time
• Spanning trees with low crossing number
• scientific article; zbMATH DE number 177542 (Why is no real title available?)
• scientific article; zbMATH DE number 742889 (Why is no real title available?)
• Maximum plane trees in multipartite geometric graphs
• Enumerating the \(k\) best plane spanning trees
• Piercing diametral disks induced by edges of maximum spanning trees
• Piercing diametral disks induced by edges of maximum spanning trees

This page was built for publication: Computing Euclidean maximum spanning trees

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