Patent Document ID: 8910095
Application ID: 13844310

Base Claim:
1. One or more non-transitory computer-readable media storing computer-executable instructions for causing one or more processors to perform a method of layout decomposition, the method comprising: receiving layout data for a layout design, the layout design corresponding to at least a portion of an integrated circuit, the layout data comprising mask assignment information for some layout features; deriving data of a coloring graph from the layout data, the coloring graph comprising vertices representing layout features in the layout design and edges between some pairs of vertices indicating the mask assignment information; performing a graph reduction process and a graph partitioning process on the coloring graph to generate a simplified coloring graph, wherein the graph reduction process comprises collapsing diamond graphs; decomposing the layout design based on the simplified coloring graph to generate decomposition information; and storing the decomposition information.

---

Claim 6:
6. The one or more non-transitory computer-readable media recited in claim 1 , wherein the decomposing further comprises: applying an exact coloring algorithm.