New Methods for the Construction of Test Cases for Partitioning Heuristics

Partitioning is an important problem in the design automation of integrated circuits. This problem in many of itsformulation is NP-Hard, and several heuristic methods have been proposed for its solution. To evaluate theeffectiveness of the various partitioning heuristics, it is desirable to have test cases with known optimal solutionsthat are as “random looking” as possible. In this paper, we describe several methods for the construction of suchtest cases. All our methods except one use the theory of network flow. The remaining method uses a relationshipbetween a partitioning problem and the geometric clustering problem. The latter problem can be solved inpolynomial time in any fixed dimension