Record Details


Field	Value

Title	A new partitioning strategy based on supermodular functions

Names	PATKAR, SACHIN BATTERYWALA, SH CHANDRAMOULI, M NARAYANAN, H
Date Issued	1997 (iso8601)
Abstract	r-way partitioning is an NP-hard problem. In this paper we present a few heuristics for clustering, which are motivated by the theory of sub/supermodular functions. The implementation based on this heuristic justifies some already published results about the approximability of the optimal solutions to this NP-hard problem using the ideas from the theory of sub/supermodular-functions. We also suggest a hypergraph model which is more natural and more suitable for modeling this problem. We give some experimental results which indicate that our methods hold promise. Our experimental results are comparable, and in some cases better than the best to date spectral partitioning methods on the standard benchmark circuits. Finally we suggest some multilevel strategies for partitioning, where in each level we employ a supermodular function based strategy which gives a suboptimal partitioning on the fused supergraph.
Genre	Article
Topic	Vlsi
Identifier	Proceedings of the Tenth International Conference on VLSI Design, Hyderabad, India, 4-7 January 1997, 32-37

ICAR Research Data Repository for Knowledge Management