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

https://hal.inria.fr/inria-00621065
Contributor : Adrien Friggeri <>
Submitted on : Friday, September 9, 2011 - 1:44:28 PM
Last modification on : Wednesday, July 8, 2020 - 12:43:07 PM
Long-term archiving on: : Saturday, December 10, 2011 - 2:23:58 AM

Files

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

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

95

Files downloads

55