The complexity of single row routing

DOI10.1109/TCS.1984.1085526MaRDI QIDQ3684052zbMATH OpenFDO

Authors Raghunath Raghavan, Sartaj Sahni

Publication date 1984

Published in IEEE Transactions on Circuits and Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/TCS.1984.1085526

zbMATH Keywords

multilayer rectilinear wire routingNP-hard

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)

Recommendations

• scientific article; zbMATH DE number 140495
• Single bend wiring on surfaces
• On optimum single-row routing
• scientific article; zbMATH DE number 4014616
• Minimizing channel density in standard cell layout

Cited in

(12)

• Minimizing channel density in standard cell layout
• The benefits of external wires in single row routing
• Single bend wiring on surfaces
• Single-row transformation of complete graphs
• scientific article; zbMATH DE number 1696838 (Why is no real title available?)
• scientific article; zbMATH DE number 4014616 (Why is no real title available?)
• Single bend wiring
• scientific article; zbMATH DE number 97100 (Why is no real title available?)
• scientific article; zbMATH DE number 140495 (Why is no real title available?)
• On optimum single-row routing
• An algorithm for the via assignment problem in multilayer backboard wiring
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is \cal NP-Complete

This page was built for publication: The complexity of single row routing

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