A Note on Balancedness of Dominating Set Games |
| |
| Authors: | Email author" target="_blank">Qizhi?FangEmail author Hye?Kyung?Kim |
| |
| Institution: | (1) Department of Mathematics, Ocean University of China, Qingdao, 266071, P.R. China;(2) Department of Mathematics, Catholic University of Daegu, Kyungsan, 712-702, Korea |
| |
| Abstract: | In this paper we consider the balancedness of dominating set games, introduced by Velzen 2003. We establish a new kind of
0-1 program formulation to model the domination problem on graphs, and give a strong connection between LP relaxation of this
0-1 program and the cost allocation problem concerning the core of a dominating set game. Duality theory on Lagrange dual
is the main technique in our proof. In particular, we use this insight to give the equivalence of the balancedness for two
different dominating set games.
Supported by NSFC (No. 10371114) and KRF-2003-002-C00038 |
| |
| Keywords: | core balancedness Lagrange dual rigid dominating set game relaxed dominating set game |
| 本文献已被 SpringerLink 等数据库收录！ |
|
