Premium
A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
Author(s) -
Sharaiha Yazid M.,
Gendreau Michel,
Laporte Gilbert,
Osman Ibrahim H.
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199705)29:3<161::aid-net4>3.0.co;2-f
Subject(s) - tabu search , spanning tree , minimum spanning tree , shortest path tree , mathematical optimization , kruskal's algorithm , prim's algorithm , computer science , k minimum spanning tree , vertex (graph theory) , heuristic , distributed minimum spanning tree , steiner tree problem , mathematics , algorithm , graph , combinatorics , tree structure , k ary tree , binary tree
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. © 1997 John Wiley & Sons, Inc. Networks 29: 161–171, 1997