Maximizing the Cohesion is NP-hard

Adrien Friggeri; Eric Fleury

Accueil
Déposer
Consulter tout HAL
Publications Inria
Recherche
Services
Documentation
OpenAccess
- Inria soutient la science ouverte

version 1

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

Adrien Friggeri ^{1, 2} AuthorId : 613564

Auteur

Eric Fleury ^{1, 2} AuthorId : 622891
Auteur

1 DNET - Dynamic Networks (LIP - Laboratoire de l'Informatique du Parallélisme Ecole Normale Supérieure de Lyon 46, allée d'Italie 69364 Lyon Cedex 07 France - France) StructId : 93134

Inria Grenoble - Rhône-Alpes (Inovallée 655 avenue de l'Europe 38330 Montbonnot - France) StructId : 2497
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France) StructId : 300009
LIP - Laboratoire de l'Informatique du Parallélisme (46 Allée d'Italie 69364 LYON CEDEX 07 - France) StructId : 35418
- ENS Lyon - École normale supérieure - Lyon (15 parvis René Descartes - BP 7000 - 69342 Lyon Cedex 07 - France) StructId : 6818
- UCBL - Université Claude Bernard Lyon 1 (43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex - France) StructId : 194495
  - Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France) StructId : 300009
- Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- CNRS - Centre National de la Recherche Scientifique : UMR5668 (France) StructId : 441569

2 IXXI - Institut Rhône-Alpin des systèmes complexes (5, Rue du Vercors 69007 Lyon - France) StructId : 145352

ENS Lyon - École normale supérieure - Lyon (15 parvis René Descartes - BP 7000 - 69342 Lyon Cedex 07 - France) StructId : 6818
UL2 - Université Lumière - Lyon 2 (86, rue Pasteur - 69007 Lyon - France) StructId : 33804
UJF - Université Joseph Fourier - Grenoble 1 (BP 53 - 38041 Grenoble Cedex 9 - France) StructId : 51016
UJML - Université Jean Moulin - Lyon III (6 cours Albert Thomas - 69008 Lyon - France) StructId : 118744
UCBL - Université Claude Bernard Lyon 1 (43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex - France) StructId : 194495
- Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
INSA Lyon - Institut National des Sciences Appliquées de Lyon (20 Avenue Albert Einstein, 69621 Villeurbanne cedex - France) StructId : 219748
- Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- INSA - Institut National des Sciences Appliquées (France) StructId : 301232
Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France) StructId : 300009
CNRS - Centre National de la Recherche Scientifique (France) StructId : 441569

Abstract : We show that the problem of finding a set with maximum cohesion in an undirected network is NP-hard.

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

Domaine :

Informatique [cs] / Réseaux et télécommunications [cs.NI]

Sciences de l'Homme et Société / Sociologie

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 1 novembre 2018 - 01:21:15
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

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

Métriques

Consultations de la notice

723

Téléchargements de fichiers

Maximizing the Cohesion is NP-hard

Fichiers

Identifiants

Collections

Citation

Exporter

Partager

Métriques

723

228

Contact