A 2.5-factor approximation algorithm for the \(k\)-MST problem

DOI10.1016/S0020-0190(98)00010-6zbMath1338.68287MaRDI QIDQ293204

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

approximation algorithms\(k\)-MST problem

Mathematics Subject Classification ID

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

Related Items (10)

Algorithms for the on-line quota traveling salesman problem ⋮ Approximation algorithms for the covering Steiner problem ⋮ A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem ⋮ A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems ⋮ Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems ⋮ Shape rectangularization problems in intensity-modulated radiation therapy ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem ⋮ Prize-Collecting TSP with a Budget Constraint ⋮ A 2-approximation for the \(k\)-prize-collecting Steiner tree problem

Cites Work

• A General Approximation Technique for Constrained Forest Problems
• Unnamed Item

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