On the complexity of single row routing problems

DOI10.1007/3-540-51542-9_44MaRDI QIDQ4028915zbMATH OpenFDO

Authors Adair Dingle, I. H. Sudborough

Publication date 28 March 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-51542-9_44

zbMATH Keywords

NP-completesingle row routing problemsVLSI

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Circuits, networks (94C99)

Recommendations

• The complexity of single row routing
• scientific article; zbMATH DE number 4077133
• VLSI routing in polynomial time
• Some polynomially solvable subcases of the detailed routing problem in VLSI design
• Switchbox routing in VLSI design: Closing the complexity gap

Cited in

(10)

• The benefits of external wires in single row routing
• Two-segmented channel routing is strong NP-complete
• Single-row transformation of complete graphs
• scientific article; zbMATH DE number 4014616 (Why is no real title available?)
• Absolute area approximation in channel routing is NP-hard
• The complexity of single row routing
• scientific article; zbMATH DE number 97100 (Why is no real title available?)
• On optimum single-row routing
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is \cal NP-Complete
• Switchbox routing in VLSI design: closing the complexity gap (extended abstract)

This page was built for publication: On the complexity of single row routing problems

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