DocumentCode
2360321
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
fYear
1988
fDate
7-9 June 1988
Firstpage
1839
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1988., IEEE International Symposium on
Conference_Location
Espoo, Finland
Type
conf
DOI
10.1109/ISCAS.1988.15294
Filename
15294
Link To Document