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 : Thursday, November 21, 2019 - 2:31:29 AM
Long-term archiving on: 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

739

Files downloads

308