Provably good routing in graphs: regular arrays
P Raghavan, CD Thompson - … annual ACM symposium on Theory of …, 1985 - dl.acm.org
P Raghavan, CD Thompson
Proceedings of the seventeenth annual ACM symposium on Theory of computing, 1985•dl.acm.orgWe examine the problem of routing wires on a VLSI chip where the nodes to be connected
are arranged in a two-dimensional array. We develop provably good algorithms that find a
solution close to the optimal one with high probability. Our approximation algorithms solve
the relevant 0-1 integer optimization problems by solving their relaxed versions and then
rounding by an interesting probabilistic technique. One of our algorithms, using
multicommodity flow, has applications to routing in circuit switching networks.
are arranged in a two-dimensional array. We develop provably good algorithms that find a
solution close to the optimal one with high probability. Our approximation algorithms solve
the relevant 0-1 integer optimization problems by solving their relaxed versions and then
rounding by an interesting probabilistic technique. One of our algorithms, using
multicommodity flow, has applications to routing in circuit switching networks.
We examine the problem of routing wires on a VLSI chip where the nodes to be connected are arranged in a two-dimensional array. We develop provably good algorithms that find a solution close to the optimal one with high probability. Our approximation algorithms solve the relevant 0-1 integer optimization problems by solving their relaxed versions and then rounding by an interesting probabilistic technique. One of our algorithms, using multicommodity flow, has applications to routing in circuit switching networks.