Maximizing the Cohesion is NP-hard

Adrien Friggeri 1, 2 Eric Fleury 1, 2
1 DNET - Dynamic Networks
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
2 IXXI - Institut Rhône-Alpin des systèmes complexes
Résumé : Nous montrons que le problème de trouver un ensemble de cohésion maximum dans un graphe non orienté est NP-dur.
Type de document :
Rapport
[Research Report] RR-7734, INRIA. 2011
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00621065
Contributeur : Adrien Friggeri <>
Soumis le : dimanche 9 octobre 2011 - 02:25:52
Dernière modification le : jeudi 12 juillet 2018 - 01:06:59
Document(s) archivé(s) le : mardi 10 janvier 2012 - 02:20:17

Fichiers

RR-7734.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00621065, version 2
  • ARXIV : 1109.1994

Collections

ENS-LYON | INRIA | INSA-LYON | INRIA-RRRT | UGA | LARA | LIP | UNIV-LYON1 | UNIV-LYON2

Citation

Adrien Friggeri, Eric Fleury. Maximizing the Cohesion is NP-hard. [Research Report] RR-7734, INRIA. 2011. 〈inria-00621065v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

714

Téléchargements de fichiers

214

Contact


archive-ouverte@inria.fr