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
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

Citation

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

Partager

Métriques

Consultations de la notice

704

Téléchargements de fichiers

205