Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Ant algorithm for determining the critical linkages in VLSI
Authors
	Zaporozhets D.Yu.
	Zaruba D.V.
	Kureichik V.V.
Date of publication
	2014
Abstract
	In this article the modified ant algorithm for determining the critical VLSI paths using the traveling salesman problem and experimental investigation of its characteristics is suggested. This algorithm is a part of the swarm intelligence method, which is one of bioinspired approaches, describing the collective behavior of a decentralized self-organizing system, containing a variety of agents (ants), locally interacting with each other and with the environment. The task of definition of the traveling salesman problem is described in suggested article. The modified ant algorithm, which is capable of obtaining suboptimal solutions sets is described. Series of tests and experiments allowed to specify the theoretical estimation of the time complexity of the algorithm and optimize their behavior for various structures of graphs. In the best case, the time complexity of the algorithm ~ O (n logn), and in the worst case - O (n3).
Keywords
	optimization, traveling salesman problem, multiagent system, the ant algorithm
Library reference
	Zaporozhets D.Yu., Zaruba D.V., Kureichik V.V. Ant algorithm for determining the critical linkages in VLSI // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2014. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2014. Part 2. P. 107-112.
URL of paper
	http://www.mes-conference.ru/data/year2014/pdf/D114.pdf