Algorithms for core stability, core largeness, exactness, and extendability of flow games

DOI10.1007/S11464-009-0048-YMaRDI QIDQ2266830zbMATH OpenOpenAlexFDO

Authors Qizhi Fang, Rudolf Fleischer, Jian Li, Xiaoxun Sun

Publication date 26 February 2010

Published in Frontiers of Mathematics in China (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11464-009-0048-y

zbMATH Keywords

algorithmcooperative gameexactnessflow networkimputationseries-parallel graph

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Cooperative games (91A12) Combinatorial games (91A46)

Review text

In this paper, the authors propose the structural characterization of exact games, extendable games, large core and stable core for simple flow games and obtain the polynomial time algorithms to test these properties. Although it is co-NP-complete to decide whether an imputation belongs to the core, this does not rule out the possibility that core stability can be decided efficiently. They also talk of some open problems.

Recommendations

• Algorithms for Core Stability, Core Largeness, Exactness, and Extendability of Flow Games
• Core Stability of Flow Games
• The Cost of Stability in Network Flow Games
• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• On the core and f-nucleolus of flow games

Cites work

• A game with no solution
• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• Algorithms for Core Stability, Core Largeness, Exactness, and Extendability of Flow Games
• Assignment games with stable core
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Cooperative games with large cores
• Core Stability of Flow Games
• Cores of convex games
• Finding nucleolus of flow game
• Generalized Network Problems Yielding Totally Balanced Games
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 1796969 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• Large cores and exactness
• Network Flow and Testing Graph Connectivity
• On the Complexity of Cooperative Solution Concepts
• Prosperty properties of TU-games
• Solving the 2-disjoint paths problem in nearly linear time
• Space efficient algorithms for directed series–parallel graphs
• The Recognition of Series Parallel Digraphs
• Topology of series-parallel networks
• Totally Balanced Games and Games of Flow

Cited in

(8)

• On computational complexity of membership test in flow games and linear production games
• Core stability in chain-component additive games
• The least-core of threshold network flow games
• On the core and f-nucleolus of flow games
• Core Stability of Flow Games
• Algorithms for Core Stability, Core Largeness, Exactness, and Extendability of Flow Games
• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• Balancedness conditions for exact games

This page was built for publication: Algorithms for core stability, core largeness, exactness, and extendability of flow games

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