Record Details

Improving graph partitions using submodular functions

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Improving graph partitions using submodular functions
 
Creator PATKAR, SB
NARAYANAN, H
 
Subject algorithms
strength
network
 
Description We investigate into the role of submodular functions in designing new heuristics and approximate algorithms to some NP-hard problems arising in the field of VLSI Design Automation. In particular, we design and implement efficient heuristic for improving a bipartition of a graph in the sense of ratioCut (Discrete Appl. Math. 90 (1999) 3; 29th Annual Symposium on Foundations of Computer Science, 1988, p. 422). We also design an approximate algorithm for another NP-hard problem which is a dual of the well-known NP-hard problem of finding a densest k-subgraph of a graph (see J. Algorithms 34 (2000) 203; Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993, p. 692). Our algorithms are based on submodular function and are implementable in polynomial time using efficient network flow based subroutines. To the best of our knowledge our algorithms are the first ones to use submodular functions based approach for the problems considered here. We also describe the experimental results which provide the evidence of our heuristic for improving the ratioCut. (C) 2002
 
Publisher ELSEVIER SCIENCE BV
 
Date 2011-07-25T07:10:08Z
2011-12-26T12:50:12Z
2011-12-27T05:36:20Z
2011-07-25T07:10:08Z
2011-12-26T12:50:12Z
2011-12-27T05:36:20Z
2003
 
Type Article
 
Identifier DISCRETE APPLIED MATHEMATICS, 131(2), 535-553
0166-218X
http://dx.doi.org/10.1016/S0166-218X(02)00472-9
http://dspace.library.iitb.ac.in/xmlui/handle/10054/6670
http://hdl.handle.net/10054/6670
 
Language en