TY - GEN

T1 - Obtaining subtrees from graphs

T2 - 2003 IEEE Swarm Intelligence Symposium, SIS 2003

AU - Gosavi, S.

AU - Das, S.

AU - Vaze, S.

AU - Singh, G.

AU - Buehler, E.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - Ant colony optimization

KW - Application software

KW - Computational modeling

KW - Computer networks

KW - Cost function

KW - Integrated circuit synthesis

KW - Polynomials

KW - Routing

KW - Simulated annealing

KW - Traveling salesman problems

UR - http://www.scopus.com/inward/record.url?scp=84942155265&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84942155265&partnerID=8YFLogxK

U2 - 10.1109/SIS.2003.1202262

DO - 10.1109/SIS.2003.1202262

M3 - Conference contribution

AN - SCOPUS:84942155265

T3 - 2003 IEEE Swarm Intelligence Symposium, SIS 2003 - Proceedings

SP - 160

EP - 166

BT - 2003 IEEE Swarm Intelligence Symposium, SIS 2003 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 24 April 2003 through 26 April 2003

ER -