An efficient rectilinear Steiner minimum tree algorithm based on ant colony optimization

Author

Hu, Yu ; Jing, Tong ; Hong, Xianlong ; Feng, Zhe ; Hu, Xiaodong ; Yan, Giriying

Author_Institution

Tsinghua Univ., Beijing, China

Volume

2

fYear

2004

Firstpage

1276

Abstract

The rectilinear Steiner minimum tree (RSMT) problem is one of the fundamental problems in physical design, especially in routing, which is known to be NP-complete. This paper presents a practical heuristic for RSMT construction based on ant colony optimization (ACO). This algorithm has been implemented on a Sun workstation with Unix operating system and the results have been compared with the GeoSteiner 3.1 and a recent work using batched greedy triple construction (BGTC). Experimental results show that our algorithm, named ACO-Steiner, can get a very short run time and keep the high performance.

Keywords

VLSI; circuit layout CAD; computational complexity; integrated circuit layout; network routing; optimisation; trees (mathematics); NP-complete problem; Sun workstation; ULSI physical design; Unix operating system; VLSI physical design; ant colony optimization; batched greedy triple construction; practical heuristic; rectilinear Steiner minimum tree algorithm; routing; Algorithm design and analysis; Ant colony optimization; Cost function; Operating systems; Routing; Steiner trees; Sun; Ultra large scale integration; Very large scale integration; Workstations;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, Circuits and Systems, 2004. ICCCAS 2004. 2004 International Conference on

Print_ISBN

0-7803-8647-7

Type

conf

DOI

10.1109/ICCCAS.2004.1346406

Filename

1346406