Improving graph partitions using submodular functions
DSpace at IIT Bombay
View Archive InfoField | 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
|
|