Layout decomposition with pairwise coloring and adaptive multi-start for triple patterning lithography

Ye Zhang*, Wai Shing Luk, Yunfeng Yang, Hai Zhou, Changhao Yan, David Z. Pan, Xuan Zeng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


In this article we present a pairwise coloring (PWC) approach to tackle the layout decomposition problem for triple patterning lithography (TPL). The main idea is to reduce the problem to a set of bi-coloring problems. The overall solution is refined by applying a bi-coloring method for pairs of color sets per pass. One obvious advantage of this method is that the existing double patterning lithography (DPL) techniques can be reused effortlessly. Moreover, we observe that each pass can be fulfilled efficiently by integrating an SPQR-tree-graph-division-based bi-coloring method. In addition, to prevent the solution getting stuck in the local minima, an adaptive multi-start (AMS) approach is incorporated. Adaptive starting points are generated according to the vote of previous solutions. The experimental results show that our method is competitive with other works on both solution quality and runtime performance.

Original languageEnglish (US)
Article number2
JournalACM Transactions on Design Automation of Electronic Systems
Issue number1
StatePublished - Nov 2015


  • Adaptive multi-start
  • Design for manufacturability
  • Layout decomposition
  • Pairwise coloring
  • Triple patterning lithography

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Layout decomposition with pairwise coloring and adaptive multi-start for triple patterning lithography'. Together they form a unique fingerprint.

Cite this