Generalized Graph Clustering: Recognizing (p,q)-Cluster

Pinar Heggerness 1 Daniel Lokshtanov 1 Jesper Nederlof 1 Christophe Paul 2 Jan Arne Telle 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Cluster Editing is a classical graph theoretic approach to tackle the problem of data set clustering: it consists of modifying a similarity graph into a disjoint union of cliques, i.e, clusters. As pointed out in a number of recent papers, the cluster editing model is too rigid to capture common features of real data sets. Several generalizations have thereby been proposed. In this paper, we introduce (p, q)-cluster graphs, where each cluster misses at most p edges to be a clique, and there are at most q edges between a cluster and other clusters. Our generalization is the first one that allows a large number of false positives and negatives in total, while bounding the number of these locally for each cluster by p and q. We show that recognizing (p, q)-cluster graphs is NP-complete when p and q are input. On the positive side, we show that (0, q)-cluster, (p, 1)-cluster, (p, 2)-cluster, and (1, 3)-cluster graphs can be recognized in polynomial time.
Type de document :
Communication dans un congrès
WG'10: International Workshop on Graph Theoretic Concepts in Computer Science, Jun 2010, Zarós, Greece. pp.12, 2010, LNCS. 〈http://wg2010.thilikos.info/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00533520
Contributeur : Christophe Paul <>
Soumis le : dimanche 7 novembre 2010 - 08:25:11
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00533520, version 1

Collections

Citation

Pinar Heggerness, Daniel Lokshtanov, Jesper Nederlof, Christophe Paul, Jan Arne Telle. Generalized Graph Clustering: Recognizing (p,q)-Cluster. WG'10: International Workshop on Graph Theoretic Concepts in Computer Science, Jun 2010, Zarós, Greece. pp.12, 2010, LNCS. 〈http://wg2010.thilikos.info/〉. 〈lirmm-00533520〉

Partager

Métriques

Consultations de la notice

220