Sharaiha, Y.M., Gendreau, M., Laporte, Gilbert, Osman, Ibrahim H. (1997) A tabu search algorithm for the capacitated shortest spanning tree problem. Networks, 29 (3). pp. 161-171. ISSN 0028-3045. (doi:10.1002/(SICI)1097-0037(199705)29:3<161::AID-NET4>3.0.CO;2-F) (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:17945)
| The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided. | |
| Official URL: http://dx.doi.org/10.1002/(SICI)1097-0037(199705)2... |
Abstract
The Capacitated Shortest Spanning Tree Problem consists of determining a shortest spanning tree in a vertex weighted graph such that the weight of every subtree linked to the root by an edge does not exceed a prescribed capacity. We propose a tabu search heuristic for this problem, as well as dynamic data structures developed to speed up the algorithm. Computational results on new randomly generated instances and on instances taken from the literature indicate that the proposed approach produces high-quality solutions within reasonable computing times. (C) 1997 John Wiley & Sons, Inc.
| Item Type: | Article |
|---|---|
| DOI/Identification number: | 10.1002/(SICI)1097-0037(199705)29:3<161::AID-NET4>3.0.CO;2-F |
| Subjects: | Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science |
| Divisions: | Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Mathematics, Statistics and Actuarial Science |
| Depositing User: | T.J. Sango |
| Date Deposited: | 13 May 2009 09:53 UTC |
| Last Modified: | 05 Nov 2024 09:53 UTC |
| Resource URI: | https://kar.kent.ac.uk/id/eprint/17945 (The current URI for this page, for reference purposes) |
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):
Altmetric
Altmetric
