Name
Abstract | ||
|---|---|---|
Abstract. Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree (mast) problem: Given a set P of n points in the plane, flnd a spanning tree of P of minimum \area," where the area of a spanning tree T is the area of the union of the n ¡ 1 disks whose diameters are the edges in T . We prove that the Euclidean minimum,spanning tree of P is a constant-factor approximation for mast. We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment (mara) problem, for the Minimum-Area Connected Disk Graph (macdg) problem, and for the Minimum-Area Tour (mat) problem. The flrst problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.comgeo.2006.03.001 | Computational Geometry: Theory and Applications |
Keywords | Field | DocType |
minimum-area tour,tree problem,salesman problem,optimization problem,minimum-area spanning tree,euclidean minimum,minimum-area connected disk,power assignment problem,constant-factor approximation,minimum-area range assignment,related natural problem,spanning tree,assignment problem | Graph theory,Discrete mathematics,Combinatorics,Minimum degree spanning tree,Euclidean minimum spanning tree,Travelling salesman problem,Assignment problem,Spanning tree,Optimization problem,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
35 | 3 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-28101-0 | 4 | 0.46 |
References | Authors | |
7 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paz Carmi | 1 | 321 | 43.14 |
| Matthew J. Katz | 2 | 225 | 19.92 |
| Joseph S.B. Mitchell | 3 | 4329 | 428.84 |