Ant colony optimization for Steiner tree problems

Authors: Prossegger, M. and Bouchachia, A.

Journal: 5th International Conference on Soft Computing as Transdisciplinary Science and Technology, CSTST '08 - Proceedings

Pages: 331-336

ISBN: 9781605580463

DOI: 10.1145/1456223.1456292


Complexity in real-world problems is often tackled by a divide-and-conquer strategy which consists of breaking down the problem into sub-problems to find local solutions. These solutions are then merged in a bottom-up fashion and optimized to produce the final solution. Applications like wiring and pipelining in urban areas are typically complex problems. They require searching the famous Minimum Steiner tree in huge graphs that model the real-world topology of the urban areas. The present paper introduces a new approach relying on the notion of divide-and-conquer to solve the Minimum Steiner tree in large graphs. This approach, called SC-IAC, combines spectral clustering and ant colony optimization in a two-stage algorithm. The first stage allows generating graph segments, whereas the second uses parallel independent ant colonies to find local and global minima of the Steiner tree. To illustrate the efficiency and accuracy of SC-IAC, large real-world benchmarks are used. Copyright 2008 ACM.

Source: Scopus

Ant colony optimization for Steiner tree problems.

Authors: Prossegger, M. and Bouchachia, A.

Editors: Chbeir, R., Badr, Y., Abraham, A., Laurent, D., Köppen, M., Ferri, F., Zadeh, L.A. and Ohsawa, Y.

Journal: CSTST

Pages: 331-336

Publisher: ACM

ISBN: 978-1-60558-046-3

Source: DBLP

Preferred by: Hamid Bouchachia