On the approximability of maximum and minimum edge clique partition problems
Författare
Summary, in English
We consider the following clustering problems: given an undirected graph, partition its vertices into disjoint clusters such that each cluster forms a clique and the number of edges within the clusters is maximized (Max-ECP), or the number of edges between clusters is minimized (Min-ECP). These problems arise naturally in the DNA clone classification. We investigate the hardness of finding such partitions and provide approximation algorithms. Further, we show that greedy strategies yield constant factor approximations for graph classes for which maximum cliques can be found efficiently.
Avdelning/ar
- Computer Science
Publiceringsår
2007
Språk
Engelska
Sidor
217-226
Publikation/Tidskrift/Serie
International Journal of Foundations of Computer Science
Volym
18
Issue
2
Dokumenttyp
Artikel i tidskrift
Förlag
World Scientific Publishing
Ämne
- Computer Science
Nyckelord
- Approximation algorithm
- inapproximability
- clique partition
- DNA clone classification
- clustering
Status
Published
Projekt
- VR 2005-4085
ISBN/ISSN/Övrigt
- ISSN: 0129-0541