Improving graph partitions using submodular functions

✍ Scribed by Sachin B. Patkar; H. Narayanan

• Book ID: 104294098
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 203 KB
• Volume: 131
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00472-9

✦ Synopsis

We investigate into the role of submodular functions in designing new heuristics and approximate algorithms to some NP-hard problems arising in the ÿeld of VLSI Design Automation. In particular, we design and implement e cient 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 ÿnding 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 e cient network ow based subroutines. To the best of our knowledge our algorithms are the ÿrst 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.