On coloring rectangular and diagonal grid graphs for multiple patterning lithography
Rattachement africain : us, il. Niveau de preuve : code pays fourni par la source.
Le résumé fourni par la source
Rectangular and diagonal grid graphs are induced subgraphs of a rectangular or diagonal grid respectively. Their k-coloring problem has direct applications in printing contact/via layouts by multi-patterning 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. In this paper, we conduct a complete analysis of the k-coloring problems on rectangular and diagonal grid graphs, and particularly the NP-completeness of 3-coloring on a diagonal grid graph is proved. In practice, we propose an exact 3-coloring algorithm. Experiments are conducted to verify its effectiveness and performance. Extensions and other results are also discussed.
Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.
Le contrôle bibliographique ouvert
DOI retrouvé dans Crossref DOI retrouvé ; titre concordant.
- Titre Crossref
- On coloring rectangular and diagonal grid graphs for multiple patterning lithography
- Date Crossref
- 01/01/2018
- Éditeur
- IEEE
- Type
- proceedings-article
Ce recoupement confirme des métadonnées liées au DOI. Il ne confirme ni la méthode ni les conclusions de l’étude, et il ne compte pas comme une seconde source scientifique indépendante.
Les institutions déclarées
Une affiliation ne permet pas de déduire la nationalité d’un auteur.