A constant-factor approximation algorithm for the \(k\)-MST problem
type: Item
instance of: scholarly article
title: A constant-factor approximation algorithm for the \(k\)-MST problem
zbMATH Open document ID: 0946.68109
author: R. Ravi
author: Santosh S. Vempala
author: Avrim Blum
published in: Journal of Computer and System Sciences
publication date: 2000-02-17T00:00:00Z
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1343330
zbMATH Keywords: undirected graph
MaRDI profile type: Publication
full work available at URL: jcss.1997.1542
OpenAlex ID: W1575625195
cites work: Q4234074
cites work: The prize collecting traveling salesman problem
cites work: The minimum latency problem
cites work: Q4234076
cites work: Weighted k‐cardinality trees: Complexity and polyhedral structure
cites work: Q4875179
cites work: A General Approximation Technique for Constrained Forest Problems
cites work: The orienteering problem
cites work: Q4875213
cites work: Q3128917
DOI: 10.1006/JCSS.1997.1542
Recommended article: Q4228499
Recommended article: Q4234076
Recommended article: A 2.5-factor approximation algorithm for the \(k\)-MST problem
Recommended article: A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
Recommended article: Q4952696
Recommended article: A Constant-Factor Approximation Algorithm for the Geometrick-MST Problem in the Plane
Recommended article: A constant-factor approximation algorithm for the \(k\)-median problem
Recommended article: A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
Recommended article: A deterministic algorithm for the MST problem in constant rounds of congested clique
Recommended article: Q5743439
description: scientific article; zbMATH DE number 1343330