Premium
Algorithms for the constrained maximum‐weight connected graph problem
Author(s) -
Lee Heungsoon Felix,
Dooly Daniel R.
Publication year - 1996
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199610)43:7<985::aid-nav4>3.0.co;2-9
Subject(s) - vertex (graph theory) , steiner tree problem , mathematics , combinatorics , graph , heuristic , computer science , mathematical optimization
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 we 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. We first show that the Steiner tree problem is a special case of the CMCG problem. Then we 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. We also present a heuristic algorithm for the CMCG problem with a general graph and its bound analysis. We 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. © 1996 John Wiley & Sons, Inc.