exploringtheconstrainedmaximumedgeweightconnectedgraphproblem

CSpace > 应用数学研究所

	exploringtheconstrainedmaximumedgeweightconnectedgraphproblem
	Zhenping Li 1; Shihua Zhang2 ; XiangSun Zhang2 ; Luonan Chen 3
	2009-01-01
发表期刊	actamathematicaeapplicataesinicaenglishseries
ISSN	0168-9673
卷号	25 期号:4 页码:697
摘要	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.
语种	英语
资助项目	[National Natural Science Foundation of China] ; [Beijing Natural Science Foundation] ; [Foundation of Beijing Education Commission] ; [Funding Project for Academic Human Resources Development in Institutions of Higher Learning Under the Jurisdiction of Beijing Municipality (PHR(IHLB))] ; [Foundation of WYJD200902]
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/40918
专题	应用数学研究所
作者单位	1.School of Information,Beijing Wuzi University 2.中国科学院数学与系统科学研究院 3.Institute of Systems Biology,Shanghai University
推荐引用方式 GB/T 7714	Zhenping Li,Shihua Zhang,XiangSun Zhang,et al. exploringtheconstrainedmaximumedgeweightconnectedgraphproblem[J]. actamathematicaeapplicataesinicaenglishseries,2009,25(4):697.
APA	Zhenping Li,Shihua Zhang,XiangSun Zhang,&Luonan Chen.(2009).exploringtheconstrainedmaximumedgeweightconnectedgraphproblem.actamathematicaeapplicataesinicaenglishseries,25(4),697.
MLA	Zhenping Li,et al."exploringtheconstrainedmaximumedgeweightconnectedgraphproblem".actamathematicaeapplicataesinicaenglishseries 25.4(2009):697.