Optimal replication for min-cut partitioning
Authors:
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 432-435
Abstract
Heuristics for replicating logic have been shown to reduce pin count and wiring density in partitioned logic networks. An efficient algorithm for determining an optimal min-cut replication set for a k-partitioned graph in O(knm log (n/sup 2//m)) time is presented. For the NP-hard case with limited size partition components, a replication heuristic which reduces the worst-case running time by a factor of O(k/sup 2/) over previous methods is proposed. Experimental results are presented.Keywords
This publication has 5 references indexed in Scilit:
- A new approach to the maximum flow problem1986
- A Linear-Time Heuristic for Improving Network Partitions1982
- A Heuristic Procedure for the Partitioning and Mapping of Computer Logic GraphsIEEE Transactions on Computers, 1971
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956