Algorithms for core stability,core largeness,exactness, and extendability of flow games |
| |
Authors: | Qizhi Fang Rudolf Fleischer Jian Li Xiaoxun Sun |
| |
Institution: | 1.Department of Mathematics,
Ocean University of China, Qingdao 266100, China; 2.Department of Computer
Science and Engineering, Fudan University, Shanghai 200433, China; 3.Department of Computer
Science, University of Maryland, College Park, MD 20742, USA; 4.Department of Mathematics
and Computing, University of Southern Queensland, Toowoomba QLD 4350,
Australia; |
| |
Abstract: | We study core stability and some related properties of flow games defined on simple networks (all edge capacities are equal)
from an algorithmic point of view. We first present a sufficient and necessary condition that can be tested efficiently for
a simple flow game to have a stable core. We also prove the equivalence of the properties of core largeness, extendability,
and exactness of simple flow games and provide an equivalent graph theoretic characterization which allows us to decide these
properties in polynomial time. |
| |
Keywords: | Flow network series-parallel graph imputation cooperative game |
本文献已被 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《Frontiers of Mathematics in China》浏览原始摘要信息 |
| 点击此处可从《Frontiers of Mathematics in China》下载免费的PDF全文 |
|