Name
Abstract | ||
|---|---|---|
We consider a natural generalization of the classical minimum spanning tree problem called Minimum Spanning Tree with Neighborhoods (MSTN)which seeks a tree of minimum length to span a set of 2D regions called neighborhoods. Each neighborhood contributes exact one node to the tree, and the MSTN has the minimum total length among all possible trees spanning the set of nodes. We prove the NP-hardness of this problem for the case in which the neighborhoods are a set of disjoint discs and rectangles. When the regions considered are a set of disjoint 2D unit discs, we present the following approximation results: (1) A simple algorithm that achieves an approximation ratio of 7.4; (2) Lower bounds and two 3-approximation algorithms; (3) A PTAS for this problem. Our algorithms can be easily generalized to higher dimensions. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-72870-2_29 | AAIM |
Keywords | Field | DocType |
minimum spanning tree,approximation ratio,3-approximation algorithm,tree problem,possible tree,following approximation result,minimum length,disjoint disc,minimum total length,classical minimum,lower bound | Discrete mathematics,Mathematical optimization,Combinatorics,Distributed minimum spanning tree,k-minimum spanning tree,K-ary tree,Euclidean minimum spanning tree,Spanning tree,Mathematics,Kruskal's algorithm,Reverse-delete algorithm,Minimum spanning tree | Conference |
Volume | ISSN | Citations |
4508 | 0302-9743 | 10 |
PageRank | References | Authors |
0.56 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yang Yang | 1 | 259 | 18.33 |
| Mingen Lin | 2 | 66 | 4.27 |
| Jinhui Xu | 3 | 665 | 78.86 |
| Yulai Xie | 4 | 54 | 9.67 |