Name
Abstract | ||
|---|---|---|
Given a set of points Q in the plane, define the r/2-Disk Graph, Q(r), as a generalized version of the Unit Disk Graph: the vertices of the graph is Q and there is an edge between two points in Q iff the distance between them is at most r. In this paper, motivated by applications in wireless sensor networks, we study the following geometric problem of color-spanning sets: given n points with m colors in the plane, choosing m points P with distinct colors such that the r/2-Disk Graph, P(r), is connected and r is minimized. When at most two points are of the same color c(i) (or, equivalently, when a color c(i) spans at most two points), we prove that the problem is NP-hard to approximate within a factor 3 - epsilon. And we present a tight factor-3 approximation for this problem. For the more general case when each color spans at most k points, we present a factor-(2k-1) approximation. Our solutions are based on the applications of the famous Hall's Marriage Theorem on bipartite graphs, which could be useful for other problems. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-45030-3_55 | ALGORITHMS AND COMPUTATION |
Field | DocType | Volume |
Graph,Discrete mathematics,Combinatorics,Linear span,Vertex (geometry),Computer science,Bipartite graph,Wireless sensor network,Unit disk graph | Conference | 8283 |
Issue | ISSN | Citations |
null | 0302-9743 | 1 |
PageRank | References | Authors |
0.36 | 21 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chenglin Fan | 1 | 28 | 7.24 |
| Jun Luo | 2 | 222 | 26.61 |
| Binhai Zhu | 3 | 903 | 109.96 |