Global wire routing in two-dimensional arrays

DOI10.1007/BF01840353zbMath0634.94024MaRDI QIDQ1097238

Umesh V. Vazirani, Clark D. Thompson, Richard M. Karp, Ronald L. Rivest, Vijay V. Vazirani, Frank Thompson Leighton

Publication date: 1987

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

linear programminginteger programmingglobal routingcomputer-aided design for integrated circuitsgate arraysregular rectangular arrayrouting wires of a VLSI chip

Mathematics Subject Classification ID

Applications of graph theory to circuits and networks (94C15)

Related Items

The pin redistribution problem in multi-chip modules, Global wire routing in two-dimensional arrays, On the kernelization of split graph problems, Approximation-Friendly Discrepancy Rounding, Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Matrix approximation and Tusnády's problem, A Stabilizing Algorithm for Finding Two Node-Disjoint Paths in Arbitrary Networks, Kernelization of Two Path Searching Problems on Split Graphs, Integer programming in VLSI design, Multicommodity flow in trees: packing via covering and iterated relaxation, Complexity of pairwise shortest path routing in the grid, ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors, Algorithms for hierarchical and semi-partitioned parallel scheduling, Unnamed Item, Minimizing maximum fiber requirement in optical networks

Cites Work

• A framework for solving VLSI graph layout problems
• Global wire routing in two-dimensional arrays
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• ``Integer-making theorems
• A decomposition algorithm for circuit routing
• Two-dimensional stochastic model for interconnections in master slice integrated circuits
• The NP-completeness column: An ongoing gulde