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

DOI10.1016/J.DAM.2017.03.007MaRDI QIDQ528547zbMATHOpenAlexFDO

Authors Kazutoshi Ando, Ryosuke Inagaki, Kazuya Shoji

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 complexityminimum spanning treecooperative gameShapley valuesubmodular function

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)

Recommendations

• Characterizations of the cycle-complete and folk solutions for minimum cost spanning tree problems
• 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
• Algorithms for computing the folk rule in minimum cost spanning tree problems with groups
• Submodularity of minimum-cost spanning tree games

Cites work

• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A fair rule in minimum cost spanning tree problems
• 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
• Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases
• Graph theory
• Minimum cost forest games
• Minimum cost spanning tree games and population monotonic allocation schemes.
• On cost allocation for a spanning tree: A game theoretic approach
• Sharing a minimal cost spanning tree: beyond the folk solution

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528547)