Nearly optimal algorithms and bounds for multilayer channel routing

DOI10.1145/201019.201037MaRDI QIDQ4369873zbMATH OpenOpenAlexFDO

Authors Bonnie Berger, Martin L. Brady, Donna J. Brown, Tom Leighton

Publication date 2 February 1998

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/201019.201037

zbMATH Keywords

routing channels

Mathematics Subject Classification ID

Computer system organization (68M99)

Recommendations

• Optimal multilayer channel routing with overlap
• scientific article; zbMATH DE number 3907789
• Optimal Three-Layer Channel Routing
• Channel routing of multiterminal nets

Cited in

(27)

• One-layer routing without component constraints
• Channel routing in knock-knee mode: Simplified algorithms and proofs
• A parallel multi-layer channel router on the HVH model
• Routing multiterminal nets on a hexagonal grid
• A near-optimal Manhattan channel router for a class of nets with the shift-right-one pattern
• A preliminary study of a diagonal channel-routing model
• Unconstrained multilayer switchbox routing
• Absolute area approximation in channel routing is NP-hard
• An efficient lower bound algorithm for channel routing
• scientific article; zbMATH DE number 6538149 (Why is no real title available?)
• scientific article; zbMATH DE number 3898776 (Why is no real title available?)
• Optimal Three-Layer Channel Routing
• scientific article; zbMATH DE number 3907789 (Why is no real title available?)
• Optimal Rotation Problems in Channel Routing
• A Provably Good Algorithm for the Two Module Routing Problem
• A 1.6 Approximation Algorithm for Routing Multiterminal Nets
• An algorithm for finding a non-trivial lower bound for channel routing
• scientific article; zbMATH DE number 1332659 (Why is no real title available?)
• Channel routing of multiterminal nets
• scientific article; zbMATH DE number 1538069 (Why is no real title available?)
• scientific article; zbMATH DE number 1786525 (Why is no real title available?)
• scientific article; zbMATH DE number 3893100 (Why is no real title available?)
• Integer Programming and Combinatorial Optimization
• Some polynomially solvable subcases of the detailed routing problem in VLSI design
• The shortest multipaths problem in a capacitated dense channel
• Optimal multilayer channel routing with overlap
• Multiterminal global routing: A deterministic approximation scheme

This page was built for publication: Nearly optimal algorithms and bounds for multilayer channel routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4369873)