Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

On the approximability of maximum and minimum edge clique partition problems

Författare

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.

Avdelning/ar

  • Computer Science

Publiceringsår

2007

Språk

Engelska

Sidor

217-226

Publikation/Tidskrift/Serie

International Journal of Foundations of Computer Science

Volym

18

Issue

2

Dokumenttyp

Artikel i tidskrift

Förlag

World Scientific Publishing

Ämne

  • Computer Science

Nyckelord

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

Status

Published

Projekt

  • VR 2005-4085

ISBN/ISSN/Övrigt

  • ISSN: 0129-0541