On the approximability of maximum and minimum edge clique partition problems

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


We consider the following clustering problems: given a general 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 (Maχ-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
Title of host publicationTheory of Computing 2006 - Proceedings of the 12th Computing
Subtitle of host publicationThe Australasian Theory Symposium, CATS 2006
Publication statusPublished - 1 Dec 2006
Externally publishedYes
EventTheory of Computing 2006 - 12th Computing: The Australasian Theory Symposium, CATS 2006 - Hobart, TAS, Australia
Duration: 16 Jan 200619 Jan 2006


ConferenceTheory of Computing 2006 - 12th Computing: The Australasian Theory Symposium, CATS 2006
CityHobart, TAS


  • Approximation algorithms
  • Clique partition

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture
  • Information Systems
  • Software

Cite this