Patent ID: 9141752
Filing Date: 2015-09-22
Classification: G06F

Abstract:
1. A method comprising: accessing data representing a layout of a layer of an integrated circuit (IC) comprising a plurality of polygons defining circuit patterns to be divided among three or more photomasks for multi-patterning a single layer of a semiconductor substrate; inputting a conflict graph having a plurality of vertices representing the circuit patterns; identifying a first vertex and a second vertex of the plurality of vertices, each of which is connected to a third vertex and a fourth vertex of the plurality of vertices, where the third and fourth vertices are connected to a same edge of the conflict graph; merging the first and second vertices to form a reduced graph having a smaller number of vertices than the conflict graph; and detecting at least one vertex in the reduced graph indicating a conflict wherein at least one of the steps of accessing, inputting, merging or detecting is performed by a computer.