| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6944854 | Microelectronics Journal | 2018 | 11 Pages |
Abstract
In recent years, a wide range of heuristic as well as exact approaches has been proposed to solve these problems. While the NP-completeness of routing and pin assignment has already been conjectured in the literature, we present the first actual proofs. Thus, the use of general-purpose approaches like SAT solvers is indeed justified. We additionally prove the NP-completeness for variants of the routing problem.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Hardware and Architecture
Authors
Oliver Keszocze, Philipp Niemann, Arved Friedemann, Rolf Drechsler,