Obtaining subtrees from graphs: An ant colony approach

S. Gosavi, S. Das, S. Vaze, G. Singh, E. Buehler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

The ant systems optimization approach is a new method of solving combinatorial optimization problems. It was originally introduced as a metaheuristic approach for the well-known traveling salesman problem. But it was subsequently shown to be an equally effective algorithm for solving other optimization problems. This article supplies more results for an extended ant colony algorithm, which can be used to compute a minimum cost Steiner tree from a graph. In each pass of the proposed algorithm, ants are placed at the terminal nodes of the Steiner tree to be computed. They are then allowed to move towards one another, along the edges of the graph, until they merge into a single entity. In this process, the paths taken by the ants define a Steiner tree. Edges receive reinforcement in the form of pheromone deposits along the paths taken by the ant, that is based on the quality of the Steiner tree produced. Pheromones eventually accrue most along better edges. As a result, after several iterations, a good Steiner tree can be extracted from the deposit. The algorithm can easily be used in several practical applications.

Original languageEnglish (US)
Title of host publication2003 IEEE Swarm Intelligence Symposium, SIS 2003 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages160-166
Number of pages7
ISBN (Electronic)0780379144, 9780780379145
DOIs
StatePublished - 2003
Externally publishedYes
Event2003 IEEE Swarm Intelligence Symposium, SIS 2003 - Indianapolis, United States
Duration: Apr 24 2003Apr 26 2003

Publication series

Name2003 IEEE Swarm Intelligence Symposium, SIS 2003 - Proceedings

Other

Other2003 IEEE Swarm Intelligence Symposium, SIS 2003
CountryUnited States
CityIndianapolis
Period4/24/034/26/03

Keywords

  • Ant colony optimization
  • Application software
  • Computational modeling
  • Computer networks
  • Cost function
  • Integrated circuit synthesis
  • Polynomials
  • Routing
  • Simulated annealing
  • Traveling salesman problems

ASJC Scopus subject areas

  • Computational Mathematics
  • Control and Optimization
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Obtaining subtrees from graphs: An ant colony approach'. Together they form a unique fingerprint.

Cite this