A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem

Journal Article

  • Author(s): Yazid M. Sharaiha, Michel Gendreau, Gilbert Laporte, Ibrahim H. Osman
  • Article first published online: 07 Dec 1998
  • DOI: 10.1002/(SICI)1097-0037(199705)29:3<161::AID-NET4>3.0.CO;2-F
  • Read on Online Library
  • Subscribe to Journal


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

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.