IEEE Transactions on Circuits and Systems · 1979 · 92 citations · 1 references
EngineeringComputer EngineeringElectrical EngineeringComputer ArchitectureComputer NetworksOptimizationCombinatorial OptimizationNetwork Flow AlgorithmsNetwork OptimizationRoutingRouting AlgorithmsCircuit RoutingCongestion OptimizationMultilayer RoutingPrinted Circuit BoardsRouting Congestion AnalysisRouting Congestion ReductionRouting Problems
The problem of single-row routing represents the backbone of the problem of general routing of multilayer printed circuit boards. In this paper, the necessary and sufficient condition for optimum single-row routing is obtained. By optimum routing we mean minimumm street congestion. A novel formulation is introduced. Examples are given to illustrate how optimum routings are derived. A graph theory interpretation of the condition is also given.
1