A constant-factor approximation algorithm for the \(k\)-MST problem
From MaRDI portal
Publication:1305925
DOI10.1006/jcss.1997.1542zbMath0946.68109MaRDI QIDQ1305925
R. Ravi, Santosh Vempala, Avrim L. Blum
Publication date: 17 February 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1997.1542
68R10: Graph theory (including graph drawing) in computer science
Related Items
A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs, Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing, Local search algorithms for the \(k\)-cardinality tree problem., An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
Cites Work