Efficient algorithms for subdominant cycle-complete cost functions and cycle-complete solutions

DOI10.1016/j.dam.2017.03.007zbMath1414.91018OpenAlexW2606528734MaRDI QIDQ528547

Kazuya Shoji, Kazutoshi Ando, Ryosuke Inagaki

Publication date: 12 May 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.03.007

zbMATH Keywords

computational complexityShapley valuesubmodular functioncooperative gameminimum spanning tree

Mathematics Subject Classification ID

Cooperative games (91A12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)

Cites Work

• Unnamed Item
• Unnamed Item
• A new stable and more responsive cost sharing solution for minimum cost spanning tree problems
• Axiomatization of the Shapley value on minimum cost spanning tree games
• Sharing a minimal cost spanning tree: beyond the folk solution
• Minimum cost forest games
• Minimum cost spanning tree games and population monotonic allocation schemes.
• Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases
• A fair rule in minimum cost spanning tree problems
• On cost allocation for a spanning tree: A game theoretic approach

This page was built for publication: Efficient algorithms for subdominant cycle-complete cost functions and cycle-complete solutions