Garg, N. ; Hochbaum, D. S. (1997) An O(logk)-approximation algorithm for thek minimum spanning tree problem in the plane Algorithmica, 18 (1). pp. 111-121. ISSN 0178-4617
Full text not available from this repository.
Official URL: http://link.springer.com/article/10.1007%2FBF02523...
Related URL: http://dx.doi.org/10.1007/BF02523691
Abstract
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(logk)-approximation algorithm.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer Verlag. |
| Keywords: | Grids; Traveling Salesman Problem |
| ID Code: | 101271 |
| Deposited On: | 31 Jan 2018 09:33 |
| Last Modified: | 31 Jan 2018 09:33 |
Repository Staff Only: item control page
