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

Department/s

  • Computer Science

Publishing year

2007

Language

English

Pages

217-226

Publication/Series

International Journal of Foundations of Computer Science

Volume

18

Issue

2

Document type

Journal article

Publisher

World Scientific Publishing

Topic

  • Computer Science

Keywords

  • Approximation algorithm
  • inapproximability
  • clique partition
  • DNA clone classification
  • clustering

Status

Published

Project

  • VR 2005-4085

ISBN/ISSN/Other

  • ISSN: 0129-0541