Back to Search
Start Over
Fixed-Parameter Tractable Algorithms for Optimal Layout Decomposition and Beyond.
- Source :
- IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems; Sep2019, Vol. 38 Issue 9, p1731-1743, 13p
- Publication Year :
- 2019
-
Abstract
- This paper studies the application of fixed-parameter tractable (FPT) algorithms to solve computer-aided design (CAD) problems. Specifically, we focus on layout decomposition problems for four lithography technologies: 1) double patterning lithography (DPL); 2) DPL with e-beam lithography; 3) DPL with directed self-assembly; and 4) DPL with directed self-assembly and e-beam lithography. Layout decomposition for the first three technologies are long-standing open problems without efficient optimal solutions, and the fourth technology is very promising in the future. The proposed approaches use ideas drastically different from all the previous works and can normally get optimal solutions in a short time. We show the great potential of applying FPT algorithms to solve more NP-hard problems efficiently in CAD. [ABSTRACT FROM AUTHOR]
- Subjects :
- NP-hard problems
LITHOGRAPHY
COMPUTER-aided design
ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 02780070
- Volume :
- 38
- Issue :
- 9
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems
- Publication Type :
- Academic Journal
- Accession number :
- 138256451
- Full Text :
- https://doi.org/10.1109/TCAD.2018.2859255