Connected set cover problem and its applications
文献类型：期刊论文
| 作者 | Shuai, Tian-Ping; Hu, Xiao-Dong
|
| 刊名 | ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS
 |
| 出版日期 | 2006 |
| 卷号 | 4041页码:243-254 |
| 关键词 | set cover approximation algorithm performance ratio wavelength assignment |
| ISSN号 | 0302-9743 |
| 英文摘要 | We study an extension of the set cover problem, the connected set cover problem, the problem is to find a set cover of minimal size that satisfies some connectivity constraint. We first propose two algorithms that find optimal solutions for two cases, respectively, and then we propose one approximation algorithm for a special case that has the best possible performance ratio. At last we consider how to apply the obtained result to solve a wavelength assignment problem in all optical networks. |
| WOS研究方向 | Computer Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000239454600023 |
| 出版者 | SPRINGER-VERLAG BERLIN |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/2862]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Shuai, Tian-Ping |
| 作者单位 | 1.Beijing Univ Posts & Telecommun, Dept Math, Beijing 100876, Peoples R China 2.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China |
| 推荐引用方式 GB/T 7714 | Shuai, Tian-Ping,Hu, Xiao-Dong. Connected set cover problem and its applications[J]. ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS,2006,4041:243-254. |
| APA | Shuai, Tian-Ping,&Hu, Xiao-Dong.(2006).Connected set cover problem and its applications.ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS,4041,243-254. |
| MLA | Shuai, Tian-Ping,et al."Connected set cover problem and its applications".ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS 4041(2006):243-254. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。