Back to Search
Start Over
On Coloring Rectangular and Diagonal Grid Graphs for Multipatterning and DSA Lithography.
- Source :
- IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems; Jun2020, Vol. 39 Issue 6, p1205-1216, 12p
- Publication Year :
- 2020
-
Abstract
- Rectangular grid graph (RGG) and diagonal grid graph (DGG) are induced subgraphs of a rectangular or diagonal grid, respectively. Their $k$ -coloring problem has direct applications in printing contact/via layouts by multipatterning lithography (MPL). However, the problem in general is computationally difficult for $k>2$ , while it remains an open question on grid graphs due to their regularity and sparsity. On the other hand, directed self-assembly (DSA) technique can work with MPL to optimize the graph by grouping neighboring vertices such that $k$ can be reduced, but the problem of deploying the grouping for coloring is even more intractable. In this paper, we study both of the $k$ -coloring problems, with and without DSA grouping, on RGG and DGG. Without grouping, a complete $k$ -coloring analysis is conducted and particularly the NP-completeness of 3-coloring on a diagonal grid is proved. When considering grouping, we present a 3-coloring solution and prove the NP-completeness to solve the problem of $k=2$. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02780070
- Volume :
- 39
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems
- Publication Type :
- Academic Journal
- Accession number :
- 143457110
- Full Text :
- https://doi.org/10.1109/TCAD.2019.2915326