Title :
An Approximation Algorithm for Max k-Uncut with Capacity Constraints
Author :
Choudhury, Salimur ; Gaur, Daya R. ; Krishnamurti, Ramesh
Author_Institution :
Math & Comput. Sc., Univ. of Lethbridge, Lethbridge, AB, Canada
Abstract :
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 ges 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.
Keywords :
bioinformatics; computational complexity; graph theory; network theory (graphs); optimisation; pattern clustering; proteins; NP-complete problem; bioinformatics; capacity constraint; clustering problem; constant factor approximation algorithm; database; edge weighted graph cut problem; max k-uncut; protein interaction network; randomly generated graph; Algorithm design and analysis; Approximation algorithms; Bioinformatics; Clustering algorithms; Computer networks; Data analysis; Gene expression; Partitioning algorithms; Performance analysis; Proteins; approximation algorithms; capacity constraints; maximum k-uncut;
Conference_Titel :
Computational Sciences and Optimization, 2009. CSO 2009. International Joint Conference on
Conference_Location :
Sanya, Hainan
Print_ISBN :
978-0-7695-3605-7
DOI :
10.1109/CSO.2009.443