Maximizing the Cohesion is NP-hard

Adrien Friggeri; Eric Fleury

HAL: inria-00621065, version 2

arXiv: 1109.1994

See short view

BibTeX,EndNote,...

Maximizing the Cohesion is NP-hard
Friggeri A., Fleury E.
Research report (2011) - http://hal.inria.fr/inria-00621065

Available versions

v1 (2011-09-09)

v2 (2011-10-09)

Type of document:

Research report

Domain:

Computer Science/Networking and Telecommunication

Humanities and Social Sciences/Sociology

Title:

Maximizing the Cohesion is NP-hard

Author(s):

Adrien Friggeri (

) ^1, 2, Eric Fleury ^1, 2

Research team(s):

1:	DNET (ENS / LIP Laboratoire de l'Informatique du Parallélisme / INRIA Grenoble Rhône-Alpes)

	École Normale Supérieure - Lyon – INRIA – Laboratoire d'informatique du Parallélisme

	LIP - Laboratoire de l'Informatique du Parallélisme Ecole Normale Supérieure de Lyon 46, allée d'Italie 69364 Lyon Cedex 07 France

	France

2:	Institut Rhône-Alpin des systèmes complexes (IXXI)

	http://www.ixxi.fr

	INRIA – École Normale Supérieure - Lyon – Institut National des Sciences Appliquées (INSA) - Lyon – Université Claude Bernard - Lyon I – Université Joseph Fourier - Grenoble I – CNRS – Institut de recherche pour le développement [IRD]

	5, Rue du Vercors 69007 Lyon

	France

Abstract:

We show that the problem of finding a set with maximum cohesion in an undirected network is NP-hard.

Abstract in french:

Nous montrons que le problème de trouver un ensemble de cohésion maximum dans un graphe non orienté est NP-dur.

Full text language:

English

Report type:

Research Report

Publication date:

2011-09-09

Internal note:

RR-7734

Attached file list to this document:

TEX

biblio.bib

(26.6 KB)

Logo-INRIA-couleur.pdf

(6.7 KB)

Logo-INRIA-couleur.ps

(35.1 KB)

(5.3 KB)

(24.4 KB)

(329.7 KB)

(23 KB)

(6.5 KB)

(19.5 KB)

(1.5 KB)

(502 B)

(3.6 KB)

(320.3 KB)

(56.4 KB)

(15.2 KB)

(20.3 KB)

PDF

RR-7734.pdf

(163.3 KB)

RR-7734.ps

(932.4 KB)


inria-00621065, version 2
http://hal.inria.fr/inria-00621065
oai:hal.inria.fr:inria-00621065
From: Adrien Friggeri <>
Submitted on: Sunday, 9 October 2011 02:25:52
Updated on: Sunday, 9 October 2011 19:07:28