Exploring the Constrained Maximum Edge-weight Connected Graph Problem  

作　　者：Zhen-ping Li Shi-hua Zhang Xiang-Sun Zhang Luo-nan Chen 

机构地区：[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

出　　处：《Acta Mathematicae Applicatae Sinica》2009年第4期697-708,共12页应用数学学报（英文版）

基　　金：supported by National Natural Science Foundation of China under Grant,No.60873205;Beijing Natural Science Foundation under Grant No. 1092011;Foundation of Beijing Education Commission under Grant No.SM200910037005;the Funding Project for Academic Human Resources Development in Institutions of Higher Learning Under the Jurisdiction of Beijing Municipality(PHR(IHLB))and Foundation of WYJD200902

摘　　要：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.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.

关 键 词：connected subgraph integer linear programming model network flow constraint Steiner network maximum edge weight  heuristic algorithm 

分 类 号：O22[理学—运筹学与控制论]