Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases

DOI10.1007/s13160-012-0078-9zbMath1254.91020OpenAlexW2035507135MaRDI QIDQ1926641

Kazutoshi Ando

Publication date: 28 December 2012

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13160-012-0078-9

zbMATH Keywords

computational complexityShapley valuecooperative game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cooperative games (91A12)

Related Items

Efficient computation of the Shapley value for large-scale linear production games ⋮ A new stable and more responsive cost sharing solution for minimum cost spanning tree problems ⋮ Efficient algorithms for subdominant cycle-complete cost functions and cycle-complete solutions ⋮ An Algorithm for Finding a Representation of a Subtree Distance ⋮ Computing Shapley values in the plane

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Axiomatization of the Shapley value on minimum cost spanning tree games
• Cost monotonicity, consistency and minimum cost spanning tree games
• Sharing a minimal cost spanning tree: beyond the folk solution
• On the complexity of testing membership in the core of min-cost spanning tree games
• Determinants of matrices related to the Pascal triangle
• Minimum cost spanning tree games and population monotonic allocation schemes.
• Computing the nucleolus of min-cost spanning tree games is NP-hard.
• The optimistic \(TU\) game in minimum cost spanning tree problems
• Characterization of the distance between subtrees of a tree by the associated tight span
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Computing 2-terminal reliability for radio-broadcast networks
• On the core and nucleolus of minimum cost spanning tree games
• REDUCTION OF ULTRAMETRIC MINIMUM COST SPANNING TREE GAMES TO COST ALLOCATION GAMES ON ROOTED TREES
• Power Indices in Spanning Connectivity Games
• Minimum cost spanning tree games
• The Relationship Between Convex Games and Minimum Cost Spanning Tree Games: A Case for Permutationally Convex Games
• Algorithmic Aspects of Vertex Elimination on Graphs
• On cost allocation for a spanning tree: A game theoretic approach