A Provably Good Algorithm for the Two Module Routing Problem

DOI10.1137/0215012MaRDI QIDQ3753505zbMATH OpenOpenAlexFDO

Authors Brenda S. Baker

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0215012

zbMATH Keywords

channel routingLSINP-hardwire routingworst-case performance bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• A linear time algorithm for optimal routing around a rectangle
• scientific article; zbMATH DE number 3907789
• Nearly optimal algorithms and bounds for multilayer channel routing
• scientific article; zbMATH DE number 3932954
• One-layer routing without component constraints

Cited in

(15)

• One-layer routing without component constraints
• Global wire routing in two-dimensional arrays
• An efficient one-side height minimization algorithm for routing around a rectangle
• scientific article; zbMATH DE number 1696838 (Why is no real title available?)
• The algorithm and application based on graphs for the symmetrical routing
• An algorithm for the solution of the two-route Johnson problem
• A linear time algorithm for optimal routing around a rectangle
• Two-dimensional stochastic model for interconnections in master slice integrated circuits
• Provably good moat routing
• scientific article; zbMATH DE number 1953174 (Why is no real title available?)
• Probability-driven routing in a datapath environment
• scientific article; zbMATH DE number 946301 (Why is no real title available?)
• Efficient breakout routing in printed circuit boards (extended abstract)
• Graph Drawing
• Optimal algorithms for adjacent side routing

This page was built for publication: A Provably Good Algorithm for the Two Module Routing Problem

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