Exploring the constrained maximum edge-weight connected graph problem

doi:10.1007/s10255-008-8829-8

CSpace > 应用数学研究所

	Exploring the constrained maximum edge-weight connected graph problem
	Li, Zhen-ping 2; Zhang, Shi-hua1 ; Zhang, Xiang-Sun1 ; Chen, Luo-nan 3,4
	2009-10-01
发表期刊	ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES
ISSN	0168-9673
卷号	25 期号:4 页码:697-708
摘要	Given an edge weighted graph, the maximum edge-weight connected graph (MECG) is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximum Edge-Weight Connected Graph problem (CMECG), which is an MECG whose candidate subgraphs must include a given set of k edges, then also called the k-CMECG. We formulate the k-CMECG into an integer linear programming model based on the network flow problem. The k-CMECG is proved to be NP-hard. For the special case 1-CMECG, we propose an exact algorithm and a heuristic algorithm respectively. We also propose a heuristic algorithm for the k-CMECG problem. Some simulations have been done to analyze the quality of these algorithms. Moreover, we show that the algorithm for 1-CMECG problem can lead to the solution of the general MECG problem.
关键词	connected subgraph integer linear programming model network flow constraint Steiner network maximum edge weight, heuristic algorithm
DOI	10.1007/s10255-008-8829-8
语种	英语
资助项目	National Natural Science Foundation of China[60873205] ; Beijing Natural Science Foundation[1092011] ; Foundation of Beijing Education Commission[SM200910037005] ; Funding Project for Academic Human Resources Development in Institutions of Higher Learning Under the Jurisdiction of Beijing Municipality (PHR(IHLB)) ; Foundation of WYJD200902
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:000269945800012
出版者	SPRINGER HEIDELBERG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/7922
专题	应用数学研究所
通讯作者	Zhang, Xiang-Sun
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China 2.Beijing Wuzi Univ, Sch Informat, Beijing 101149, Peoples R China 3.Shanghai Univ, Inst Syst Biol, Shanghai 200444, Peoples R China 4.Osaka Sangyo Univ, Dept Elect & Elect Engn, Osaka 5748530, Japan
推荐引用方式 GB/T 7714	Li, Zhen-ping,Zhang, Shi-hua,Zhang, Xiang-Sun,et al. Exploring the constrained maximum edge-weight connected graph problem[J]. ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,2009,25(4):697-708.
APA	Li, Zhen-ping,Zhang, Shi-hua,Zhang, Xiang-Sun,&Chen, Luo-nan.(2009).Exploring the constrained maximum edge-weight connected graph problem.ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,25(4),697-708.
MLA	Li, Zhen-ping,et al."Exploring the constrained maximum edge-weight connected graph problem".ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES 25.4(2009):697-708.