Games induced by the partitioning of a graph

Abstract : The paper aims at generalizing the notion of restricted game on a communication graph, introduced by Myerson. We consider communication graphs with weighted edges, and we define arbitrary ways of partitioning any subset of a graph, which we call correspondences. A particularly useful way to partition a graph is obtained by computing the strength of the graph. The strength of a graph is a measure introduced in graph theory to evaluate the resistance of networks under attacks, and it provides a natural partition of the graph (called the Gusfield correspondence) into resistant components. We perform a general study of the inheritance of superadditivity and convexity for the restricted game associated with a given correspondence. Our main result is to give for cycle-free graphs necessary and sufficient conditions for the inheritance of convexity of the restricted game associated with the Gusfield correspondence.
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-00830291
Contributeur : Alexandre Skoda <>
Soumis le : mardi 4 juin 2013 - 16:28:58
Dernière modification le : mardi 27 mars 2018 - 11:48:05
Document(s) archivé(s) le : jeudi 5 septembre 2013 - 04:24:00

Fichier

aor11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Michel Grabisch, Alexandre Skoda. Games induced by the partitioning of a graph. Annals of Operations Research, Springer Verlag, 2012, 201 (1), pp.229-249. 〈10.1007/s10479-012-1200-8〉. 〈hal-00830291〉

Partager

Métriques

Consultations de la notice

447

Téléchargements de fichiers

177