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
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 : Friday, November 6, 2020 - 4:04:39 AM
Long-term archiving on: : Tuesday, January 10, 2012 - 2:20:17 AM

Files

Vignette du document
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 | LARA | LIP | UNIV-LYON1 | UNIV-LYON2 | UNIV-LYON3 | INSA-GROUPE | UDL | UGA

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

770

Files downloads

426

 

Contact                    Legal Notice                    Personal Data