Decomposition algorithms for the maximum-weight connected graph problem

Decomposition algorithms for the maximum-weight connected graph problem

0.00 Avg rating0 Votes
Article ID: iaor19992524
Country: United States
Volume: 45
Issue: 8
Start Page Number: 817
End Page Number: 837
Publication Date: Dec 1998
Journal: Naval Research Logistics
Authors: ,
Abstract:

Given a positive integer R and a weight for each vertex in a graph, the maximum-weight connected graph problem (MCG) is to find a connected subgraph with R vertices that maximizes the sum of their weights. MCG has applications to communication network design and facility expansion. The constrained MCG (CMCG) is MCG with a constraint that one predetermined vertex must be included in the solution. In this paper, we introduce a class of decomposition algorithms for MCG. These algorithms decompose MCG into a number of small CMCGs by adding vertices one at a time and building a partial graph. They differ in the ordering of adding vertices. Proving that finding an ordering that gives the minimum number of CMCGs is NP-complete, we present three heuristic algorithms. Experimental results show that these heuristics are very effective in reducing computation and that different orderings can significantly affect the number of CMCGs to be solved.

Reviews

Required fields are marked *. Your email address will not be published.