On the approximability of maximum and minimum edge clique partition problems
(2006) The Australasian Theory Symposium (CATS) In Conferences in Research and Practice in Information Technology Series 168. p.101105 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 (MaxECP), or the number of edges between clusters is minimized (MinECP). 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:
http://lup.lub.lu.se/record/623064
 author
 Dessmark, Anders ^{LU} ; Jansson, Jesper ^{LU} ; Lingas, Andrzej ^{LU} ; Lundell, EvaMarta ^{LU} and Persson, Mia ^{LU}
 organization
 publishing date
 2006
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 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)
 external identifiers

 Scopus:84863559579
 ISBN
 1920682333
 14451336
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 28cf700ed0a0499681426210bc794e15 (old id 623064)
 alternative location
 http://crpit.com/abstracts/CRPITV51Dessmark.html
 date added to LUP
 20071126 09:59:31
 date last changed
 20161013 04:46:00
@misc{28cf700ed0a0499681426210bc794e15, 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 (MaxECP), or the number of edges between clusters is minimized (MinECP). 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, EvaMarta and Persson, Mia}, isbn = {1920682333}, language = {eng}, pages = {101105}, publisher = {ARRAY(0xa675ad0)}, series = {Conferences in Research and Practice in Information Technology Series}, title = {On the approximability of maximum and minimum edge clique partition problems}, volume = {168}, year = {2006}, }