Fiche du document
- handle: 10670/1.qoxtde
- halshs: halshs-01382502
info:eu-repo/semantics/OpenAccess
Mots-clés
graph complexity supermodularity partitions communication networks cooperative game convex game restricted game AMS 91 - Game theory, economics, social and behavioral/91A - Game theory/91A12 - Cooperative games91 - Game theory, economics, social and behavioral/91A - Game theory/91A43 - Games involving graphs90 - Operations research, mathematical programming/90C - Mathematical programming/90C27 - Combinatorial optimization05 -Combinatorics/05C - Graph theory/05C75 - Structural characterization of types of graphs68 - Computer science/68Q - Theory of computing/68Q25 - Analysis of algorithms and problem complexitySujets proches
divertissement jeuxCiter ce document
Alexandre Skoda, « Complexity of inheritance of F-convexity for restricted games induced by minimum partitions », HAL-SHS : économie et finance, ID : 10670/1.qoxtde
Métriques
Partage / Export
Résumé
Let G = (N,E,w ) be a weighted communication graph (with weight function w on E ). For every subset A ⊆ N, we delete in the subset E (A ) of edges with ends in A, all edges of minimum weight in E (A ). Then the connected components of the corresponding induced subgraph constitue a partition of A that we Pmin(A ). For every game (N , v ), we define the Pmin-restricted game (N , v ) by v (A = ∑F∈ Pmin (A) v(F ) for all A ⊆ N. We prove that we can decide in polynomial time if there is inheritance of F-convexity from N , v ) to the Pmin-restricted game (N , v ) where F-convexity is obtained by restricting convexity to connected subsets