Computing the nucleolus of min-cost spanning tree games is NP-hard.

DOI10.1007/s001820050083zbMath1058.91511MaRDI QIDQ1972596

Jeroen Kuipers, Ulrich Faigle, Walter Kern

Publication date: 11 April 2000

Published in: International Journal of Game Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s001820050083

zbMATH Keywords

\(N\) -person game

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

91A12: Cooperative games

Related Items

Finding nucleolus of flow game, An efficient characterization of submodular spanning tree games, Computing the nucleolus of weighted cooperative matching games in polynomial time, On the core and nucleolus of directed acyclic graph games, Path cooperative games, Computing the least-core and nucleolus for threshold cardinality matching games, Fair cost allocations under conflicts - a game-theoretic point of view -, Computational complexity in additive hedonic games, Characterization sets for the nucleolus in balanced games, The nucleolus of arborescence games in directed acyclic graphs, NP-completeness in hedonic games, Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases, An algorithm to compute the nucleolus of shortest path games, Network disconnection games: a game theoretic approach to checkpoint evaluation in networks, Computing the nucleolus of weighted voting games in pseudo-polynomial time, On the complexity of nucleolus computation for bipartite \(b\)-matching games, Arboricity games: the core and the nucleolus, The Complexity of the Nucleolus in Compact Games, The Least-Core and Nucleolus of Path Cooperative Games, COALITION FORMATION GAMES: A SURVEY