Constructing Test Cases for Partitioning Heuristics

In analyzing the effectiveness of min-cut partitioning heuristics, we are faced with the task of constructing ``random'' looking test networks with a prescribed cut-set size in its optimal partition. We present a technique for constructing networks over a given set of components that has been a priori partitioned into two parts. The networks have the property that the optimal partition, i.e., one that minimizes the size of the cut-set, is the predefined partition, and this partition has a cut-set of a given size. Furthermore, these networks can be designed to possess certain statistical properties, such as a desired mean and standard deviation for the number of components per net, so that they truly reflect the input space in the application domain. We also extend these techniques to the generalized partitioning problem.