Skip to Main content Skip to Navigation
Reports

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
Abstract : We show that the problem of finding a set with maximum cohesion in an undirected network is NP-hard.
Complete list of metadatas

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/inria-00621065
Contributor : Adrien Friggeri <>
Submitted on : Sunday, October 9, 2011 - 2:25:52 AM
Last modification on : Monday, February 10, 2020 - 12:17:01 PM
Document(s) archivé(s) le : Tuesday, January 10, 2012 - 2:20:17 AM

Files

RR-7734.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

744

Files downloads

364