On the approximability of maximum and minimum edge clique partition problems
(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:
https://lup.lub.lu.se/record/629382
- author
- Dessmark, Anders ; Jansson, Jesper ; Lingas, Andrzej LU ; Lundell, Eva-Marta LU and Persson, Mia LU
- organization
- publishing date
- 2007
- 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 Publishing
- 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
- 2016-04-01 12:38:47
- date last changed
- 2022-02-11 17:44:28
@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}}, keywords = {{Approximation algorithm; inapproximability; clique partition; DNA clone classification; clustering}}, language = {{eng}}, number = {{2}}, pages = {{217--226}}, publisher = {{World Scientific Publishing}}, 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}}, doi = {{10.1142/S0129054107004656}}, volume = {{18}}, year = {{2007}}, }