On the approximability of maximum and minimum edge clique partition problems

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

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 proceeding › Conference article published in proceeding or book › Academic research › peer-review

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 (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 language	English
Title of host publication	Theory of Computing 2006 - Proceedings of the 12th Computing
Subtitle of host publication	The Australasian Theory Symposium, CATS 2006
Volume	51
Publication status	Published - 1 Dec 2006
Externally published	Yes
Event	Theory of Computing 2006 - 12th Computing: The Australasian Theory Symposium, CATS 2006 - Hobart, TAS, Australia Duration: 16 Jan 2006 → 19 Jan 2006

Conference

Conference	Theory of Computing 2006 - 12th Computing: The Australasian Theory Symposium, CATS 2006
Country/Territory	Australia
City	Hobart, TAS
Period	16/01/06 → 19/01/06

Keywords

Approximation algorithms
Clique partition

ASJC Scopus subject areas

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

Cite this

@inproceedings{06914788053c42f8b5cdca056d0be441,

title = "On the approximability of maximum and minimum edge clique partition problems",

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 (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.",

keywords = "Approximation algorithms, Clique partition",

author = "Anders Dessmark and Jansson, {Jesper Andreas} and Andrzej Lingas and Lundell, {Eva Marta} and Mia Persson",

year = "2006",

month = dec,

day = "1",

language = "English",

isbn = "1920682333",

volume = "51",

booktitle = "Theory of Computing 2006 - Proceedings of the 12th Computing",

note = "Theory of Computing 2006 - 12th Computing: The Australasian Theory Symposium, CATS 2006 ; Conference date: 16-01-2006 Through 19-01-2006",

}

Dessmark, A, Jansson, JA, Lingas, A, Lundell, EM & Persson, M 2006, On the approximability of maximum and minimum edge clique partition problems. in Theory of Computing 2006 - Proceedings of the 12th Computing: The Australasian Theory Symposium, CATS 2006. vol. 51, Theory of Computing 2006 - 12th Computing: The Australasian Theory Symposium, CATS 2006, Hobart, TAS, Australia, 16/01/06.

On the approximability of maximum and minimum edge clique partition problems. / Dessmark, Anders; Jansson, Jesper Andreas; Lingas, Andrzej et al.
Theory of Computing 2006 - Proceedings of the 12th Computing: The Australasian Theory Symposium, CATS 2006. Vol. 51 2006.

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - On the approximability of maximum and minimum edge clique partition problems

AU - Dessmark, Anders

AU - Jansson, Jesper Andreas

AU - Lingas, Andrzej

AU - Lundell, Eva Marta

AU - Persson, Mia

PY - 2006/12/1

Y1 - 2006/12/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Clique partition

UR - http://www.scopus.com/inward/record.url?scp=84863559579&partnerID=8YFLogxK

M3 - Conference article published in proceeding or book

SN - 1920682333

SN - 9781920682330

VL - 51

BT - Theory of Computing 2006 - Proceedings of the 12th Computing

T2 - Theory of Computing 2006 - 12th Computing: The Australasian Theory Symposium, CATS 2006

Y2 - 16 January 2006 through 19 January 2006

ER -

On the approximability of maximum and minimum edge clique partition problems

Abstract

Conference

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this