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

In English

Författare

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.

Avdelning/ar

  • Computer Science

Publiceringsår

2006

Språk

Engelska

Sidor

101-105

Publikation/Tidskrift/Serie

Conferences in Research and Practice in Information Technology Series

Volym

168

Dokumenttyp

Konferensbidrag

Förlag

Australian Computer Society

Ämne

  • Computer Science

Conference name

The Australasian Theory Symposium (CATS)

Conference date

2006-01-16 - 2006-01-19

Conference place

Hobart, Australia

Status

Published

Projekt

  • VR 2005-4085

ISBN/ISSN/Övrigt

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