A High-Density Multilayer PCB Router Based on Necessary and Sufficient Conditions for Single Row Routing
- 1 January 1981
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper presents the necessary and sufficient conditions for routability of a list of two-point nets to be wired in a single row without using vias (single row routing) in a different formulation from that in [9]. These conditions are expressed in terms of left and right block counts (number of left and right blockages that will be encountered by each net if all nets in the list are routed in the same channel) of nets in the net list. An efficient routing algorithm which exploits these necessary and sufficient conditions is presented. Experimental results demonstrating the effectiveness of this algorithm are also given. Possible practical applications exploiting this set of necessary and sufficient conditions are suggested.Keywords
This publication has 6 references indexed in Scilit:
- On optimum single-row routingIEEE Transactions on Circuits and Systems, 1979
- A Topologically Based Non-Minimum Distance Routing AlgorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Special Feature New Chip Carrier Package ConceptsComputer, 1977
- The multilayer routing problem: Algorithms and necessary and sufficient conditions for the single-row, single-layer caseIEEE Transactions on Circuits and Systems, 1976
- The interconnection problem: A tutorialComputer, 1974
- Wire routing by optimizing channel assignment within large aperturesPublished by Association for Computing Machinery (ACM) ,1971