Complexity of the Minimum Base Game on Matroids

DOI10.1287/MOOR.22.1.146MaRDI QIDQ4339378zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

\(\tau\)-valuematroid theoryminimum base gameminimum spanning tree gameoracle-polynomial algorithmShapley value

Mathematics Subject Classification ID

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

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

Cited in

(7)

• Some new results on generalized additive games
• Cooperative games on simplicial complexes
• Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
• Approximating the least core value and least core of cooperative games with supermodular costs
• COALITION FORMATION GAMES: A SURVEY
• Approximate cores of submodular cost set cover games
• The investment management game: extending the scope of the notion of core

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)