Networks · 2001 · 55 citations · 3 references
Natural SciencesComputer ScienceComputational GeometryDesign OptimizationOptimizationCombinatorial OptimizationConstrained OptimizationDiscrete OptimizationHeuristic OptimizationInteger ProgrammingOptimization TheoryBranch-and-cutConvex RelaxationsLinear Programming RelaxationsMinimum Spanning Tree AlgorithmsMinimum Spanning Tree Problem
Abstract This article describes eight formulations for the Generalized Minimum Spanning Tree Problem (GMSTP). Relationships between the polytopes of their linear relaxations are established. It is shown that four of these polytopes are strictly included in the remaining ones. This analysis suggests which formulations should be preferred for the construction of a branch‐and‐cut algorithm and for the evaluation of heuristics. © 2002 John Wiley & Sons, Inc.
3
A theorem on flows in networks
David Gale · Pacific Journal of Mathematics · 1957 · 504 citations · Full text
A catalog of steiner tree formulations
Michel X. Goemans, Young‐Soo Myung · Networks · 1993 · 166 citations
On the generalized minimum spanning tree problem
Young‐Soo Myung, Chang‐Ho Lee, Dong‐wan Tcha · Networks · 1995 · 149 citations