Some polynomially solvable subcases of the detailed routing problem in VLSI design

DOI10.1016/S0166-218X(01)00225-6zbMath0998.68233WikidataQ127677626 ScholiaQ127677626MaRDI QIDQ5954248

András Recski

Publication date: 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

switchbox routing

Mathematics Subject Classification ID

Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Related Items (1)

A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods

Cites Work

• Optimal multilayer channel routing with overlap
• Disjoint paths in a rectilinear grid
• Two-layer channel routing with vertical unit-length overlap
• On the difficulty of Manhattan channel routing
• Unconstrained multilayer switchbox routing
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete
• A $2d - 1$ Lower Bound for Two-Layer Knock-Knee Channel Routing
• Channel routing of multiterminal nets
• Nearly optimal algorithms and bounds for multilayer channel routing
• The NP-completeness column: An ongoing guide
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some polynomially solvable subcases of the detailed routing problem in VLSI design