A new relaxation method for the generalized minimum spanning tree problem

Pop, P.C. and Kern, W. and Still, G.J. (2006) A new relaxation method for the generalized minimum spanning tree problem. European Journal of Operational Research, 170 (3). pp. 900-908. ISSN 0377-2217

PDF
Restricted to UT campus only: Request a copy
298Kb

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 -hard. We present several mixed integer programming formulations of the problem. Based on a new formulation of the problem we give a new solution procedure that finds the optimal solution of the GMST problem for graphs with nodes up to 240. We discuss the advantages of our approach in comparison with earlier methods.
Item Type:	Article
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/63650
Official URL:	http://dx.doi.org/10.1016/j.ejor.2004.07.058
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 238282