Conflict detection for self-aligned multiple patterning compliance

A method for performing design layout, comprising:

• receiving an initial design layout associated with an electrical component;
• generating a conflict graph from the initial design layout, the conflict graph comprising:
• a first node representing a first polygon of the initial design layout;
• a second node representing a second polygon of the initial design layout, the second node coupled to the first node by a same-process edge;
• and
• a third node representing a third polygon of the initial design layout, the third node coupled to the second node by a different-process edge;
• updating the conflict graph to remove the same-process edge and generate an updated conflict graph;
• and
• for respective loops within the updated conflict graph, identifying a conflict associated with the initial design layout based upon a loop comprising an odd number of nodes.

A method for performing design layout, comprising:

• receiving an initial design layout associated with an electrical component;
• generating a conflict graph from the initial design layout, the conflict graph comprising:
• a first node representing a first polygon of the initial design layout;
• a second node representing a second polygon of the initial design layout, the second node coupled to the first node by a same-process edge;
• and
• a third node representing a third polygon of the initial design layout, the third node coupled to the second node by a different-process edge;
• clustering the first node and the second node into a multi-node cluster responsive to the second node being coupled to the first node by the same-process edge to generate an updated conflict graph;
• and
• for respective loops within the updated conflict graph, identifying a conflict associated with the initial design layout based upon a loop comprising an odd number of nodes.