Method of determining colorability of a semiconductor device and system for implementing the same

A system for determining colorability of a layer of a semiconductor device, the system comprising:

• a non-transitory computer readable medium configured to store instructions thereon;
• and
• a processor connected to the non-transitory computer readable medium, wherein the processor is configured to execute the instructions for:
• receiving a conflict graph;
• iteratively decomposing the conflict graph to remove all nodes having fewer links than a threshold number of links;
• comparing the decomposed conflict graph with a stored conflict graph;
• determining whether the decomposed conflict graph is colorable based on the comparison;
• and
• flagging violations in response to a determination that the decomposed conflict graph is not colorable.

A method of determining colorability of a layer of a semiconductor device, the method comprising:

• determining a number of masks used to pattern the layer of the semiconductor device;
• determining a threshold number of links based on the determined number of masks;
• iteratively decomposing a conflict graph to remove all nodes having fewer links than the threshold number of links;
• comparing the decomposed conflict graph and a stored conflict graph;
• determining whether the conflict graph is colorable based on the comparison;
• and
• flagging violations in response to a determination that the decomposed conflict graph is not colorable.