Advanced

On the approximability of maximum and minimum edge clique partition problems

Dessmark, Anders; Jansson, Jesper; Lingas, Andrzej LU ; Lundell, Eva-Marta LU and Persson, Mia LU (2007) In International Journal of Foundations of Computer Science 18(2). p.217-226
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Approximation algorithm, inapproximability, clique partition, DNA clone classification, clustering
in
International Journal of Foundations of Computer Science
volume
18
issue
2
pages
217 - 226
publisher
World Scientific
external identifiers
  • wos:000250926300003
  • scopus:34247236729
ISSN
0129-0541
DOI
10.1142/S0129054107004656
project
VR 2005-4085
language
English
LU publication?
yes
id
0e39f9a8-ae82-4f76-b13d-3ec668732b9f (old id 629382)
date added to LUP
2007-11-27 15:15:02
date last changed
2017-02-19 03:42:54
@article{0e39f9a8-ae82-4f76-b13d-3ec668732b9f,
  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.},
  author       = {Dessmark, Anders and Jansson, Jesper and Lingas, Andrzej and Lundell, Eva-Marta and Persson, Mia},
  issn         = {0129-0541},
  keyword      = {Approximation algorithm,inapproximability,clique partition,DNA clone classification,clustering},
  language     = {eng},
  number       = {2},
  pages        = {217--226},
  publisher    = {World Scientific},
  series       = {International Journal of Foundations of Computer Science},
  title        = {On the approximability of maximum and minimum edge clique partition problems},
  url          = {http://dx.doi.org/10.1142/S0129054107004656},
  volume       = {18},
  year         = {2007},
}