Maximizing the Cohesion is NP-hard - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2011

Maximizing the Cohesion is NP-hard

(1, 2) , (1, 2)
1
2

Abstract

We show that the problem of finding a set with maximum cohesion in an undirected network is NP-hard.
Nous montrons que le problème de trouver un ensemble de cohésion maximum dans un graphe non orienté est NP-dur.

Domains

Computer Science [cs] Networking and Internet Architecture [cs.NI] Humanities and Social Sciences Sociology
Fichier principal
Vignette du fichier
RR-7734.pdf (137.67 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Adrien Friggeri  : Connect in order to contact the contributor

https://hal.inria.fr/inria-00621065

Submitted on : Sunday, October 9, 2011-2:25:52 AM

Last modification on : Wednesday, October 26, 2022-8:16:45 AM

Long-term archiving on: Tuesday, January 10, 2012-2:20:17 AM

Download

Dates and versions

inria-00621065 , version 1 (09-09-2011)
inria-00621065 , version 2 (09-10-2011)

Identifiers

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

Cite

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

Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

Collections

ENS-LYON UNIV-LYON3 UGA CNRS INRIA UNIV-LYON1 UNIV-LYON2 INSA-LYON INRIA-RRRT INRIA2 LARA INSA-GROUPE UDL
293 View
166 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More