Faster geometric k-point MST approximation

DOI10.1016/S0925-7721(96)00021-1zbMATH Open0889.68145OpenAlexW2010303431MaRDI QIDQ1370933FDOQ1370933

Authors: 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

Recommendations

• scientific article; zbMATH DE number 1263205
• An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane
• Publication:4952696

zbMATH Keywords

minimum spanning tree

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

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

This page was built for publication: Faster geometric \(k\)-point MST approximation

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