Abstract
In this thesis, we study two layout pattern classification problems respectively subject to an area match constraint and an edge displacement constraint. Given a circuit layout and a set of markers, each problem asks to identify a layout clip around each marker and divide the set of layout clips into disjoint clusters such that without violating a given area match constraint or edge displacement constraint, the resultant number of clusters is as small as possible and the maximum cluster size is as large as possible. Either area match constraint or edge displacement constraint is used to well capture the similarity relations between clips and to group similar clips into a cluster. We model each problem as a graph problem (i.e., a constrained minimum dominating set problem) and solve it by an integer linear programming based method. A clip merging technique for graph size reduction is also presented to accelerate our algorithms. The efficacy of our algorithms is well supported by encouraging experimental results.