A 2.5-factor approximation algorithm for the k-MST problem

DOI10.1016/S0020-0190(98)00010-6MaRDI QIDQ293204zbMATH OpenFDO

Authors Sunil Arya, H. Ramesh

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098000106?np=y

zbMATH Keywords

\(k\)-MST problemapproximation algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• A constant-factor approximation algorithm for the \(k\)-MST problem
• scientific article; zbMATH DE number 1757947
• scientific article; zbMATH DE number 1445374
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• scientific article; zbMATH DE number 1256763

Cites work

• A General Approximation Technique for Constrained Forest Problems
• scientific article; zbMATH DE number 1263205 (Why is no real title available?)

Cited in

(15)

• A constant-factor approximation algorithm for the \(k\)-MST problem
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
• scientific article; zbMATH DE number 1256763 (Why is no real title available?)
• Approximation algorithms for the covering Steiner problem
• scientific article; zbMATH DE number 1757947 (Why is no real title available?)
• scientific article; zbMATH DE number 1445374 (Why is no real title available?)
• Prize-collecting TSP with a budget constraint
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Shape rectangularization problems in intensity-modulated radiation therapy
• A 2-approximation for the \(k\)-prize-collecting Steiner tree problem
• A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems
• Bicriterial approximation for the incremental prize-collecting Steiner-tree problem
• Algorithms for the on-line quota traveling salesman problem

This page was built for publication: A 2.5-factor approximation algorithm for the \(k\)-MST problem

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