DocumentCode :
2824172
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
Volume :
2
fYear :
2009
fDate :
24-26 April 2009
Firstpage :
934
Lastpage :
938
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Sciences and Optimization, 2009. CSO 2009. International Joint Conference on
Conference_Location :
Sanya, Hainan
Print_ISBN :
978-0-7695-3605-7
Type :
conf
DOI :
10.1109/CSO.2009.443
Filename :
5194096
Link To Document :
بازگشت