CSpace  > 应用数学研究所
Zhenping Li1; Shihua Zhang2; XiangSun Zhang2; Luonan Chen3
Source Publicationactamathematicaeapplicataesinicaenglishseries
AbstractGiven 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.
Funding Project[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]
Document Type期刊论文
Affiliation1.School of Information,Beijing Wuzi University
3.Institute of Systems Biology,Shanghai University
Recommended Citation
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.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhenping Li]'s Articles
[Shihua Zhang]'s Articles
[XiangSun Zhang]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhenping Li]'s Articles
[Shihua Zhang]'s Articles
[XiangSun Zhang]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhenping Li]'s Articles
[Shihua Zhang]'s Articles
[XiangSun Zhang]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.