### Abstract

We consider the Generalized Minimum Spanning Tree Problem denoted by GMSTP. It is known that GMSTP is NP-hard and even finding a near optimal solution is NP-hard. We introduce a new mixed integer programming formulation of the problem which contains a polynomial number of constraints and a polynomial number of variables. Based on this formulation we give an heuristic solution, a lower bound procedure and an upper bound procedure and present the advantages of our approach in comparison with an earlier method. We present a solution procedure for solving GMST problem using cutting planes.

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Publication status | Published - 2000 |

### Publication series

Name | |
---|---|

Publisher | Department of Applied Mathematics, University of Twente |

No. | 1542 |

ISSN (Print) | 0169-2690 |

### Keywords

- MSC-90C11
- IR-65729
- EWI-3362
- MSC-90C35

## Cite this

Pop, P. C., Kern, W., & Still, G. J. (2000).

*The generalized minimum spanning tree problem*. Enschede: University of Twente, Department of Applied Mathematics.