Title :
A new scheme for the Steiner problem in graphs
Author :
Ji, Yu-Bo ; Liu, Mei-Lun
Author_Institution :
Dept. of Comput. Eng. & Autom., Fushun Pet. Inst., China
Abstract :
The Steiner problem in graphs has found important application in global and detailed routeing of integrated circuit layout. A scheme is described which does not immediately construct a tree, but first obtains an initial tree, and then concentrates on refining it. A loop method for refining is presented, and an algorithm is developed. The algorithm is of low time and space complexity, and experimental results show that it performs well.<>
Keywords :
circuit layout CAD; graph theory; trees (mathematics); Steiner problem in graphs; algorithm; complexity; initial tree; integrated circuit layout; loop method for refining; Application software; Application specific integrated circuits; Approximation algorithms; Automation; Costs; Integrated circuit layout; Petroleum; Routing; Steiner trees; Tree graphs;
Conference_Titel :
Circuits and Systems, 1988., IEEE International Symposium on
Conference_Location :
Espoo, Finland
DOI :
10.1109/ISCAS.1988.15294
