Patent Document ID: 9659141
Application ID: 14833364
Patent Status: 1

Claim One:
1. A system comprising: a non-transitory, computer readable storage medium for storing data representing a layout of a layer of an integrated circuit (IC) comprising a plurality of polygons defining circuit patterns to be divided among a number (N) of photomasks for multi-patterning a single layer of a semiconductor substrate, where N is greater than two; an electronic design automation (EDA) tool configured for: inputting a first conflict graph having a plurality of vertices representing the circuit patterns and a plurality of edges representing spaces smaller than a predetermined distance between adjacent vertices; identifying first and second pairs of vertices within the plurality of vertices, as candidate circuit patterns for inclusion in a same one of the photomasks, the first pair including a first vertex, the second pair including a second vertex, the first and second pairs of vertices including a common third vertex; replacing the first, second, and third vertices with a single vertex to form a reduced conflict graph, the single vertex representing the circuit patterns corresponding to the first and second pairs of vertices; and identifying a multi-patterning conflict in the reduced conflict graph, if the first and second vertices are connected by one of the edges in the first conflict graph.