An O( k)-approximation algorithm for the k minimum spanning tree problem in the plane

DOI10.1007/BF02523691zbMATH Open0866.68076OpenAlexW1537901463MaRDI QIDQ679454FDOQ679454

Authors: Dorit S. Hochbaum, Naveen Garg 

Publication date: 29 May 1997

Published in: Algorithmica (Search for Journal in Brave)

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

Recommendations

• An \(O(\log k)\) approximation algorithm for the \(k\) minimum spanning tree problem in the plane
• scientific article; zbMATH DE number 1263205
• Faster geometric \(k\)-point MST approximation
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs

zbMATH Keywords

traveling salesman problemgridsminimum tree

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• \(k\)-edge subgraph problems
• Finding k points with minimum diameter and related 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?)
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• Title not available (Why is that?)
• Faster geometric \(k\)-point MST approximation

Cited In (13)

• Multitask \(n\)-vehicle exploration problem: complexity and algorithm
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
• An \(O(\log k)\) approximation algorithm for the \(k\) minimum spanning tree problem in the plane
• Revisiting dynamic programming for finding optimal subtrees in trees
• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
• Local search algorithms for the \(k\)-cardinality tree problem.
• The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches
• A note on the $k$-minimum spanning tree problem on circles
• Minimum spanning tree of line segments
• A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
• New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem

This page was built for publication: An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane

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