Sökning: id:"swepub:oai:lup.lub.lu.se:0e39f9a8-ae82-4f76-b13d-3ec668732b9f" >
On the approximabil...
On the approximability of maximum and minimum edge clique partition problems
-
Dessmark, Anders (författare)
-
Jansson, Jesper (författare)
-
- Lingas, Andrzej (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
visa fler...
-
- Lundell, Eva-Marta (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
- Persson, Mia (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
visa färre...
-
(creator_code:org_t)
- 2007
- 2007
- Engelska.
-
Ingår i: International Journal of Foundations of Computer Science. - 0129-0541. ; 18:2, s. 217-226
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Approximation algorithm
- inapproximability
- clique partition
- DNA clone classification
- clustering
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas