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.
Fichier principal
Vignette du fichier
RR-7734.pdf (137.67 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

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⟩
293 View
166 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More