Channel routing of multiterminal nets
Authors:
Open Access
- 1 July 1994
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 41 (4) , 791-818
Abstract
This paper presents new upper bounds for channel routing of multiterminal nets, which answers the long-standing open question whether or not multiterminal problems really require channels two times wider than 2-terminal problems. We transform any multiterminal problem of density d into a so-called extended simple channel routing problem (ESCRP) of density 3d /2 + O√ d log d) . We then descibe routing algorithms for solving ESCRPs in three different models. The channel width w is ≤ 3d/2 +O(√d log d) in the knock-knee and unit-vertical-overlap models, and w ≤ 3d/2 + O√d log d) + O(ƒ) in the Manhattan model, where f is the flux of the problem. In all three cases, we improve the best-known upper bounds.Keywords
This publication has 6 references indexed in Scilit:
- Probabilistic construction of deterministic algorithms: Approximating packing integer programsJournal of Computer and System Sciences, 1988
- Routing through a generalized switchboxJournal of Algorithms, 1986
- Channel Routing Algorithms for Overlap ModelsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- Optimal Three-Layer Channel RoutingIEEE Transactions on Computers, 1984
- Disjoint paths in a rectilinear gridCombinatorica, 1982
- New Lower Bounds for Channel Width1981