Given a positive integer R and a weight for each vertex in a graph, the maximum-weight connected graph (MCG) problem is to find a connected subgraph with R vertices that maximizes the sum of the weights. The MCG problem is strongly NP-complete, and the authors study a special case of it: the constrained MCG (CMCG) problem, which is the MCG problem with a constraint of having a predetermined vertex included in the solution. They first show that the Steiner tree problem is a special case of the CMCG problem. Then the authors present three optimization algorithms for the CMCG problem. The first two algorithms deal with special graphs (tree and layered graphs) and employ different dynamic programming techniques, solving the CMCG problem in polynomial times. The third one deals with a general graph and uses a variant of the Balas additive method with an imbedded connectivity test and a pruning method. The authors also present a heuristic algorithm for the CMCG problem with a general graph and its bound analysis. They combine the two algorithms, heuristic and optimization, and present a practical solution method to the CMCG problem. Computational results are reported and future research issues are discussed.
