A Topologically Based Non-Minimum Distance Routing Algorithm
- 1 January 1978
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In this paper, a unique topologically based non-minimum distance routing algorithm is presented. It offers both maximal completion rates and minimal via usage. The algorithm is based on a topological transformation of a significant subset of the PC routing problem: A broad channel encompassing a full row of DIPs and all routes within it. This transformation eliminates the need to consider detailed path shapes during routing. The routing problem is transformed into a permutation of nets. It is coupled with a backtrack search to produce a powerful routing algorithm. The search is conducted in a planar environment.Keywords
This publication has 7 references indexed in Scilit:
- The multilayer routing problem: Algorithms and necessary and sufficient conditions for the single-row, single-layer caseIEEE Transactions on Circuits and Systems, 1976
- Wire routing by optimizing channel assignment within large aperturesPublished by Association for Computing Machinery (ACM) ,1971
- Automated printed circuit routing with a stepping apertureCommunications of the ACM, 1969
- Cellular wiring and the cellular modeling techniquePublished by Association for Computing Machinery (ACM) ,1969
- A solution to line-routing problems on the continuous planePublished by Association for Computing Machinery (ACM) ,1969
- Backtrack ProgrammingJournal of the ACM, 1965
- An Algorithm for Path Connections and Its ApplicationsIEEE Transactions on Electronic Computers, 1961