Exploring the constrained maximum edge-weight connected graph problem
文献类型：期刊论文
| 作者 | Li, Zhen-ping2; Zhang, Shi-hua1 ; Zhang, Xiang-Sun1; Chen, Luo-nan3,4
|
| 刊名 | ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES
 |
| 出版日期 | 2009-10-01 |
| 卷号 | 25期号:4页码:697-708 |
| 关键词 | connected subgraph integer linear programming model network flow constraint Steiner network maximum edge weight, heuristic algorithm |
| ISSN号 | 0168-9673 |
| DOI | 10.1007/s10255-008-8829-8 |
| 英文摘要 | 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[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记录号 | WOS:000269945800012 |
| 出版者 | SPRINGER HEIDELBERG |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/7921]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。