Double-row planar routing and permutation layout

DOI10.1002/net.3230120307zbMath0489.94040OpenAlexW2057197877MaRDI QIDQ3952043

Ernest S. Kuh, Shuji Tsukiyama

Publication date: 1982

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230120307

zbMATH Keywords

NP-completenessinterval graphical representationlayout for integrated circuits and printed circuit boardspolynomial-time heuristic algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Permutations, words, matrices (05A05) Deterministic network models in operations research (90B10) Circuits, networks (94C99) Discrete mathematics in relation to computer science (68R99)

Related Items

General circular permutation layout ⋮ Multilayer grid embeddings for VLSI ⋮ A lower bound on the area of permutation layouts

Cites Work

• The multilayer routing problem: Algorithms and necessary and sufficient conditions for the single-row, single-layer case
• On optimum single-row routing