New models of the generalized minimum spanning tree problem

New models of the generalized minimum spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor2005720
Country: Netherlands
Volume: 3
Issue: 2
Start Page Number: 153
End Page Number: 166
Publication Date: Apr 2004
Journal: Journal of Mathematical Modelling and Algorithms
Authors:
Keywords: programming: dynamic, programming: linear
Abstract:

We consider a generalization of the Minimum Spanning Tree Problem, called the Generalized Minimum Spanning Tree Problem, denoted by GMST. It is known that the GMST problem is NP-hard. We present a stronger result regarding its complexity, mainly, the GMST problem is NP-hard even on trees as well as an exact exponential time algorithm for the problem based on dynamic programming. We describe new mixed integer programming models of the GMST problem, mainly containing a polynomial number of constraints. We establish relationships between the polytopes corresponding to their linear relaxations. Based on a new model of the GMST we present a solution procedure that solves the problem to optimality for graphs with nodes up to 240. We discuss the advantages of our method in comparison with earlier methods.

Reviews

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