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

DOI10.1007/BF02523691zbMath0866.68076OpenAlexW1537901463MaRDI QIDQ679454

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

zbMATH Keywords

gridstraveling salesman problemminimum tree

Mathematics Subject Classification ID

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

Related Items (8)

Revisiting dynamic programming for finding optimal subtrees in trees ⋮ Multitask \(n\)-vehicle exploration problem: complexity and algorithm ⋮ The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches ⋮ 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 ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation ⋮ Local search algorithms for the \(k\)-cardinality tree problem.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(k\)-edge subgraph problems
• Faster geometric \(k\)-point MST approximation
• Finding k points with minimum diameter and related problems
• Weighted k‐cardinality trees: Complexity and polyhedral structure

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