✦ LIBER ✦

A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem

✍ Scribed by Sharaiha, Yazid M.; Gendreau, Michel; Laporte, Gilbert; Osman, Ibrahim H.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 150 KB
Volume: 29
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199705)29:3<161::aid-net4>3.0.co;2-f

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Dual algorithms for the shortest path tr

Dual algorithms for the shortest path tree problem

✍ Pallottino, Stefano; Scutell�, Maria Grazia 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB 👁 1 views

We consider dual approaches for the Shortest Path Tree problem. After a brief introduction to the problem, we review the most important dual algorithms which have been described in the literature for its solution and propose a new family of dual ascent algorithms. In these algorithms, ''local'' and

A tabu search heuristic for the Steiner

A tabu search heuristic for the Steiner Tree Problem

✍ Gendreau, Michel; Larochelle, Jean-Francois; Sans�, Brunilde 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 342 KB 👁 1 views

The Steiner Tree Problem (STP) in graphs is a well-known NP-hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as ATM, since it appears as the inherent mathematical structure behind multicast communications. In this paper, we present a tabu se

A tabu-search-based algorithm for contin

A tabu-search-based algorithm for continuous multiminima problems

✍ Francesco Franzè; Nicolò Speciale 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 1 views

A hierarchy of hop-indexed models for th

A hierarchy of hop-indexed models for the Capacitated Minimum Spanning Tree Problem

✍ Gouveia, Luis; Martins, Pedro 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB 👁 2 views

The Capacitated Minimum Spanning Tree Problem (CMSTP) is to find a minimum spanning tree subject to an additional constraint stating that the number of nodes in each subtree pending from a given root node is not greater than a given number Q. Gouveia and Martins (1996) proposed a hop-indexed flow mo

A note on genetic algorithms for degree-

A note on genetic algorithms for degree-constrained spanning tree problems

✍ Zhou, Gengui; Gen, Mitsuo 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 58 KB 👁 1 views

The degree-constrained spanning tree problem is of high practical importance. Up to now, there are few effective algorithms to solve this problem because of its NP-hard complexity. In this paper, we present a new approach to solve this problem by using genetic algorithms and computational results to

A branch and cut method for the degree-c

A branch and cut method for the degree-constrained minimum spanning tree problem

✍ L. Caccetta; S.P. Hill 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 2 views