Record Details

Application of fast DC analysis to partitioning hypergraphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Application of fast DC analysis to partitioning hypergraphs
 
Creator TRIVEDI, G
NARAYANAN, H
 
Description Partitioning is an important technique for solving graph based problems. The quality of partitions produced by standard methods, for example Fiduccia and Mattheyses (FM) algorithm, depends on the initial random seed partition. In order to get the best partitions, we have to run the partitioner many times with different seed partitions. In this paper, we present a heuristic for producing good seed partitions for partitioning graphs and hypergraphs by analyzing an appropriately derived resistor, current source electrical network and sorting the nodes according to their potentials. This is feasible because we use a special purpose DC analyzer which is very fast and can handle circuits of size up to a million nodes. Experiments have been performed on IBM benchmark hypergraphs on a Pentium-4 machine having 1GB RAM. For larger size hypergraphs, our method outperforms the standard random seed based FM algorithm both in terms of the partitioning time and in terms of the cut-cost.
 
Publisher IEEE
 
Date 2011-10-24T23:31:27Z
2011-12-15T09:11:49Z
2011-10-24T23:31:27Z
2011-12-15T09:11:49Z
2007
 
Type Proceedings Paper
 
Identifier 2007 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS, VOLS 1-11,3407-3410
978-1-4244-0920-4
0277-674X
http://dx.doi.org/10.1109/ISCAS.2007.378299
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15541
http://hdl.handle.net/100/2313
 
Source IEEE International Symposium on Circuits and Systems,New Orleans, LA,MAY 27-30, 2007
 
Language English