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
2 IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : We show that the problem of finding a set with maximum cohesion in an undirected network is NP-hard.
Document type :
Reports
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

Collections

ENS-LYON | CNRS | INRIA | INSA-LYON | INRIA-RRRT | UGA | LARA | LIP | UNIV-LYON1 | UNIV-LYON2 | UNIV-LYON3 | INSA-GROUPE | UDL

Citation

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

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

739

Files downloads

308

Contact


archive-ouverte@inria.fr