Tight Approximation Bounds for Connectivity with a Color-Spanning Set
文献类型：会议论文
| 作者 | Fan, Chenglin; Luo, Jun; Zhu, Binhai |
| 出版日期 | 2013 |
| 会议名称 | 24th International Symposium on Algorithms and Computation, ISAAC 2013 |
| 会议地点 | Hong Kong |
| 英文摘要 | 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. |
| 收录类别 | EI |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/5132]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | 2013 |
| 推荐引用方式 GB/T 7714 | Fan, Chenglin,Luo, Jun,Zhu, Binhai. Tight Approximation Bounds for Connectivity with a Color-Spanning Set[C]. 见:24th International Symposium on Algorithms and Computation, ISAAC 2013. Hong Kong. |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。