DocumentCode
912618
Title
An Efficient Single-Row Routing Algorithm
Author
Tarng, Tom Tsan-Kuo ; Marek-Sadowska, Malgorzata ; Kuh, Ernest S.
Author_Institution
Department of Electrical Engineering and the Computer Sciences and the Electronics Research Laboratory, University of California, Berkeley, CA, USA
Volume
3
Issue
3
fYear
1984
fDate
7/1/1984 12:00:00 AM
Firstpage
178
Lastpage
183
Abstract
In this paper, we present a heuristic algorithm for single-row routing. Our approach is based on the interval graphical representation of the given net list. The objective function for minimization is the street congestion. The problem is known to be intractable in the sense of NP-completeness, thus a polynomial-time heuristic algorithm is proposed. It has been implemented and tested with various examples. So far it has always produced optimal solutions.
Keywords
Circuit testing; Computational Intelligence Society; Helium; Heuristic algorithms; Joining processes; Minimization; Polynomials; Printed circuits; Routing; Terminology;
fLanguage
English
Journal_Title
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher
ieee
ISSN
0278-0070
Type
jour
DOI
10.1109/TCAD.1984.1270073
Filename
1270073
Link To Document