The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

On the approximability of maximum and minimum edge clique partition problems

På svenska

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2006

Language

English

Pages

101-105

Publication/Series

Conferences in Research and Practice in Information Technology Series

Volume

168

Document type

Conference paper

Publisher

Australian Computer Society

Topic

  • Computer Science

Conference name

The Australasian Theory Symposium (CATS)

Conference date

2006-01-16 - 2006-01-19

Conference place

Hobart, Australia

Status

Published

Project

  • VR 2005-4085

ISBN/ISSN/Other

  • ISBN: 1-920682-33-3
  • ISBN: 1445-1336