Obtaining subtrees from graphs: An ant colony approach

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

Research output: Chapter in Book/Entry/PoemConference contribution

5 Scopus citations


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.
Number of pages7
ISBN (Electronic)0780379144, 9780780379145
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


Other2003 IEEE Swarm Intelligence Symposium, SIS 2003
Country/TerritoryUnited States


  • 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


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

Cite this