1980 · 17 citations · 4 references
EngineeringComputer EngineeringElectrical EngineeringCircuit TheoryComputer ArchitectureOptimizationCombinatorial OptimizationIntegrated Circuit DesignLayout OptimizationRoutingRouting AlgorithmsVery-large-scale Integration LayoutPlacement AlgorithmsVery-large-scale IntegrationWire SizingWirelength Optimization
A wire-routing problem which arises commonly in the layout of circuits for very large scale integration (VLSI) is discussed. Given the coordinates of terminals u1, u2, ..., un of one component and v1, v2, ..., vn of another, the problem is to lay out n wires so that the ith wire connects ui to vi, and adjacent wires are separated at least by some fixed distance. The solution with minimum wire length is characterized, and an optimal algorithm which constructs it is presented.
4
Complexity of the mover's problem and generalizations
John H. Reif · 1979 · 769 citations
Geometric intersection problems
Michael Ian Shamos, Dan Hoey · 1976 · 465 citations
Some NP-complete geometric problems
M. R. Garey, Ron Graham, David Johnson · 1976 · 396 citations