Exploring the constrained maximum edge-weight connected graph problem |
| |
| Authors: | Zhen-ping Li Shi-hua Zhang Xiang-Sun Zhang Luo-nan Chen |
| |
| Institution: | [1]School of Information, Beijing Wuzi University, Beijing 101149, China [2]Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China [3]Institute of Systems Biology, Shanghai University, Shanghai 200444, China [4]Department of Electrical Engineering and Electronics, Osaka Sangyo University, Osaka 574-8530, Japan |
| |
| 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. |
| |
| Keywords: | connected subgraph integer linear programming model network flow constraint Steiner network maximum edge weight heuristic algorithm |
| 本文献已被 维普 SpringerLink 等数据库收录！ |
|
