Faster geometric \(k\)-point MST approximation

DOI10.1016/S0925-7721(96)00021-1zbMath0889.68145OpenAlexW2010303431MaRDI QIDQ1370933

David Eppstein

Publication date: 28 October 1997

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(96)00021-1

zbMATH Keywords

minimum spanning tree

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, Local search algorithms for the \(k\)-cardinality tree problem.

Cites Work

• Iterated nearest neighbors and finding minimal polytopes
• An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane
• Parallel construction of quadtrees and quality triangulations
• Static and dynamic algorithms for k-point clustering problems
• Steiner Minimal Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item