Abstract
In this paper, we study a cell-based row-structure layout decomposition problem for triple patterning lithography (TPL) which asks to minimize a weighted sum of coloring conflicts and stitches. We show how to extend a prior graph-based approach to solve the problem optimally under certain assumptions. Furthermore, several methods to substantially reduce the graph size and hence to accelerate the extended approach are presented. Experimental results show that our decomposer can significantly outperform a state-of-the-art work in terms of both solution quality and run time.