UNIGE document Scientific Article
previous document  unige:26174  next document
add to browser collection

An Ant Algorithm for the Steiner Tree Problem in Graphs

Luyet, Luc
Varone, Sacha
Published in Lecture Notes in Computer Science. 2007, vol. 4448, p. 42-51
Abstract 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, since it is the mathematical structure behind multi-cast communications. The goal of this paper is to design an ant algorithm (called ANT-STP) for the STP in graphs which is better than TM, which is a greedy constructive method for the STP proposed in [34]. We derive ANT-STP from TM as follows: each ant is a constructive heuristic close to TM, but the population of ants can collaborate by exchanging information by the use of the trail systems. Inm addition, the decision rule used by each individual ant is different from the decision rule used in TM. We compare TM and ANT-STP on a set of benchmark problems of the OR-Library.
Full text
Article (Published version) (418 Kb) - private document Private access
(ISO format)
LUYET, Luc, VARONE, Sacha, ZUFFEREY, Nicolas. An Ant Algorithm for the Steiner Tree Problem in Graphs. In: Lecture Notes in Computer Science, 2007, vol. 4448, p. 42-51. https://archive-ouverte.unige.ch/unige:26174

191 hits

0 download


Deposited on : 2013-02-04

Export document
Format :
Citation style :