Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On the approximability of maximum and minimum edge clique partition problems

Dessmark, Anders LU ; Jansson, Jesper LU ; Lingas, Andrzej LU ; Lundell, Eva-Marta LU and Persson, Mia LU (2006) The Australasian Theory Symposium (CATS) 168. p.101-105
Abstract
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 (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 approxi mations for graph classes for which maximum cliques can be found efficiently.
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Conferences in Research and Practice in Information Technology Series
volume
168
pages
101 - 105
publisher
Australian Computer Society
conference name
The Australasian Theory Symposium (CATS)
conference location
Hobart, Australia
conference dates
2006-01-16 - 2006-01-19
external identifiers
  • scopus:84863559579
ISBN
1-920682-33-3
1445-1336
project
VR 2005-4085
language
English
LU publication?
yes
id
28cf700e-d0a0-4996-8142-6210bc794e15 (old id 623064)
alternative location
http://crpit.com/abstracts/CRPITV51Dessmark.html
date added to LUP
2016-04-04 11:29:09
date last changed
2022-01-29 21:58:37
@inproceedings{28cf700e-d0a0-4996-8142-6210bc794e15,
  abstract     = {{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 (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 approxi mations 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}},
  booktitle    = {{Conferences in Research and Practice in Information Technology Series}},
  isbn         = {{1-920682-33-3}},
  language     = {{eng}},
  pages        = {{101--105}},
  publisher    = {{Australian Computer Society}},
  title        = {{On the approximability of maximum and minimum edge clique partition problems}},
  url          = {{http://crpit.com/abstracts/CRPITV51Dessmark.html}},
  volume       = {{168}},
  year         = {{2006}},
}