.png){kind=icon}
.png){kind=icon}
Return
A new relaxation method for the generalized minimum spanning tree problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2004.07.058.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 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. (c) 2004 Elsevier B.V. All rights reserved.
Keywords:
combinatorial optimization
minimum spanning trees
generalized minimum spanning tree problem
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W
Organization
No organization information available