An O(log k)-approximation algorithm for the k minimum spanning tree problem in the plane
An O(log k)-approximation algorithm for the k minimum spanning tree problem in the plane
复制标题
DOI：
10.1007/bf02523691
复制
发表时间：
1997-05-01
期刊：
影响因子：
1.1
通讯作者：
Hochbaum, DS
中科院分区：
文献类型：
--
作者：
Garg, N;Hochbaum, DS
给定欧氏平面上的n个点，我们考虑寻找生成任意k个点的最小树的问题。该问题是NP-困难的，我们给出了一个O（logk）-近似算法。
Given n points in the Euclidean plane, we consider the problem of finding the minimum tree spanning any k points. The problem is NP-hard and we give an O (log k)-approximation algorithm.