On some geometric problems of color-spanning sets
文献类型：期刊论文
| 作者 | Ju, Wenqi; Fan, Chenglin; Luo, Jun; Zhu, Binhai; Daescu, Ovidiu |
| 刊名 | Journal of Combinatorial Optimization
 |
| 出版日期 | 2013 |
| 英文摘要 | In this paper we study several geometric problems of color-spanning sets: given n points with m colors in the plane, selecting m points with m distinct colors such that some geometric properties of the m selected points are minimized or maximized. The geometric properties studied in this paper are the maximum diameter, the largest closest pair, the planar smallest minimum spanning tree, the planar largest minimum spanning tree and the planar smallest perimeter convex hull. We propose an O(n (1+epsilon) ) time algorithm for the maximum diameter color-spanning set problem where epsilon could be an arbitrarily small positive constant. Then, we present hardness proofs for the other problems and propose two efficient constant factor approximation algorithms for the planar smallest perimeter color-spanning convex hull problem. |
| 收录类别 | SCI |
| 原文出处 | http://link.springer.com/article/10.1007/s10878-012-9458-y |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/5060]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | Journal of Combinatorial Optimization |
| 推荐引用方式 GB/T 7714 | Ju, Wenqi,Fan, Chenglin,Luo, Jun,et al. On some geometric problems of color-spanning sets[J]. Journal of Combinatorial Optimization,2013. |
| APA | Ju, Wenqi,Fan, Chenglin,Luo, Jun,Zhu, Binhai,&Daescu, Ovidiu.(2013).On some geometric problems of color-spanning sets.Journal of Combinatorial Optimization. |
| MLA | Ju, Wenqi,et al."On some geometric problems of color-spanning sets".Journal of Combinatorial Optimization (2013). |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。