An approzimation algorithm for maz k-uncut with capacity constraints

摘要：

Clusters in protein interaction networks can potentially help identify functional relationships among proteins. The clustering problem can be modeled as a graph cut problem. Given an edge weighted graph the problem is to partition the vertices of the graph into k partitions of prescribed sizes such that the total weight of the edges within partitions are maximized. This problem is NP-complete for all k ≥ 2. We give a constant factor approximation for small k and uniform partition sizes. When the number of partitions k is 2, we give an approximation algorithm with performance ratio (p - 2)/p where p > 1 is the ratio of the sizes of the partitions. We evaluate the algorithms on the database of interacting proteins and on randomly generated graphs. Our experiments show that the algorithms are fast and have good performance ratio in practise.

作者: Salimur Choudhury Daya R.Gaur Ramesh Krishnamurti

作者单位: Math and Computer Sc.University of Lethbridge Lethbridge, AB, Canada School of Computing Sc.Simon Fraser University Burnaby, BC, Canada

会议类型: 国际会议

会议名称: The Second International Joint Conference on Computational Science and Optimization(CSO 2009)(2009 国际计算科学与优化会议)

会议地点: 三亚

会议语种:英文

页码: 1984-1988

在线出版日期: 2009-04-24（万方平台首次上网日期，不代表论文的发表时间）