Solving Medium to Large Sized Euclidean Generalized Minimum Spanning Tree Problems

Diptesh Ghosh (diptesh@iima.ac.in)

No WP2003-08-02, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: The generalized minimum spanning tree problem is a generalization of the minimum spanning tree problem. This network design problems finds several practical applications, especially when one considers the design of a large-capacity backbone network connecting several individual networks. In this paper we study the performance of six neighborhood search heuristics based on tabu search and variable neighborhood search on this problem domain. Our principal finding is that a tabu search heuristic almost always provides the best quality solution for small to medium sized instances within short execution times while variable neighborhood decomposition search provides the best quality solutions for most large instances.

Date: 2003-08-02
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.iima.ac.in/sites/default/files/rnpfiles/2003-08-02DipteshGhosh.pdf English Version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iim:iimawp:wp01770

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by (respub@iima.ac.in).