scientific article; zbMATH DE number 1332659

zbMATH Open0924.68087MaRDI QIDQ4259980FDOQ4259980

Authors: Martin Middendorf 

Publication date: 8 September 1999

Title of this publication is not available (Why is that?)

Recommendations

• On the difficulty of Manhattan channel routing
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete
• Minimum Manhattan network is NP-complete
• Minimum Manhattan network is NP-complete
• Two-segmented channel routing is strong NP-complete
• scientific article; zbMATH DE number 3967925
• Absolute area approximation in channel routing is NP-hard
• An algorithm for finding a non-trivial lower bound for channel routing
• Nearly optimal algorithms and bounds for multilayer channel routing
• A near-optimal Manhattan channel router for a class of nets with the shift-right-one pattern

zbMATH Keywords

Manhattan channel routing

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (5)

• Switchbox routing in VLSI design: Closing the complexity gap
• Title not available (Why is that?)
• Some polynomially solvable subcases of the detailed routing problem in VLSI design
• Title not available (Why is that?)
• On the difficulty of Manhattan channel routing

This page was built for publication:

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