CSpace  > 应用数学研究所
 exploringtheconstrainedmaximumedgeweightconnectedgraphproblem Zhenping Li1; Shihua Zhang2; XiangSun Zhang2; Luonan Chen3 2009-01-01 Source Publication actamathematicaeapplicataesinicaenglishseries ISSN 0168-9673 Volume 25Issue:4Pages:697 Abstract 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. Language 英语 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 期刊论文 Identifier http://ir.amss.ac.cn/handle/2S8OKBNM/40918 Collection 应用数学研究所 Affiliation 1.School of Information,Beijing Wuzi University2.中国科学院数学与系统科学研究院3.Institute of Systems Biology,Shanghai University Recommended CitationGB/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 Bookmark 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