Complexity of the Minimum Base Game on Matroids

DOI10.1287/MOOR.22.1.146zbMATH Open0871.90121OpenAlexW2157841626MaRDI QIDQ4339378FDOQ4339378

Authors: Hiroshi Nagamochi, Dao-Zhi Zeng, Naohisa Kabutoya, Toshihide Ibaraki 

Publication date: 5 October 1997

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b53f12ecbd516f5aed38b7bd490c61f76442348a

Recommendations

• Note on the computational complexity of least core concepts for min-cost spanning tree games.
• On the Complexity of Cooperative Solution Concepts
• Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases
• On the complexity of testing membership in the core of min-cost spanning tree games

zbMATH Keywords

Shapley valuematroid theory\(\tau\)-valueminimum base gameminimum spanning tree gameoracle-polynomial algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cooperative games (91A12) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (5)

• Some new results on generalized additive games
• Cooperative games on simplicial complexes
• Approximating the least core value and least core of cooperative games with supermodular costs
• Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
• COALITION FORMATION GAMES: A SURVEY

This page was built for publication: Complexity of the Minimum Base Game on Matroids

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