On the approximability of maximum and minimum edge clique partition problems

Anders Dessmark, Andrzej Lingas, Eva Marta Lundell, Mia Persson, Jesper Andreas Jansson

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)217-226
Number of pages10
JournalInternational Journal of Foundations of Computer Science
Volume18
Issue number2
DOIs
Publication statusPublished - 1 Apr 2007
Externally publishedYes

Keywords

  • Approximation algorithm
  • Clique partition
  • Clustering
  • DNA clone classification
  • Inapproximability

ASJC Scopus subject areas

  • Computer Science (miscellaneous)

Cite this