Connected set cover problem and its applications

CSpace > 应用数学研究所

	Connected set cover problem and its applications
	Shuai, Tian-Ping ; Hu, Xiao-Dong
	2006
发表期刊	ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS
ISSN	0302-9743
卷号	4041 页码:243-254
摘要	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.
关键词	set cover approximation algorithm performance ratio wavelength assignment
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Theory & Methods ; Mathematics, Applied
WOS记录号	WOS:000239454600023
出版者	SPRINGER-VERLAG BERLIN
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/2863
专题	应用数学研究所
通讯作者	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.