Constructing Test Cases for Partitioning Heuristics
- 1 September 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (9) , 1112-1114
- https://doi.org/10.1109/TC.1987.5009543
Abstract
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.Keywords
This publication has 6 references indexed in Scilit:
- Graph bisection algorithms with good average case behaviorCombinatorica, 1987
- An Improved Min-Cut Algonthm for Partitioning VLSI NetworksIEEE Transactions on Computers, 1984
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A Placement Capability Based on PartitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- A proper model for the partitioning of electrical circuitsPublished by Association for Computing Machinery (ACM) ,1972
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970