Journal of the Korean Data and Information Science Society

The Korean Data and Information Science Society (한국데이터정보과학회)
권호 표지

Balancedness of generalized fractional domination games

일반화된 분수 지배게임에 대한 균형성

  • Kim, Hye-Kyung (Department of Mathematics, Catholic University of Daegu) ;
  • Park, Jun-Pyo (Department of Mathematics, Kyungpook National University)
  • Published : 2009.01.31
Download PDF
⟨ Previous Next ⟩

Abstract

A cooperative game often arises from domination problem on graphs and the core in a cooperative game could be the optimal solution of a linear programming of a given game. In this paper, we define a {k}-fractional domination game which is a specific type of fractional domination games and find the core of a {k}-fractional domination game. Moreover, we may investigate the balancedness of a {k}-fractional domination game using a concept of a linear programming and duality. We also conjecture the concavity for {k}-fractional dominations game which is important problem to find the elements of the core.

게임이론 중 특히 협력게임은 종종 그래프에서의 지배문제로에 기인하며, 협력게임에서의 코어는 바로 이에 대한 선형프로그램의 최적해가 될 수 있다. 이 논문에서는, 분수 지배게임의 특수한 형태인 분수 지배게임을 새롭게 정의하며, 분수 지배게임의 코어를 찾는다. 더욱이 선형 프로그래밍과 그 쌍대성 개념을 이용하여 {k}-분수 지배게임의 균형성을 조사한다. 또한 코어의 원소를 찾기 위한 중요한 문제가 되는 오목성에 있어서 분수 지배게임도 오목성을 가질 것이라고 추축해본다.

Keywords

References

  1. Ahn, Y. A. (2008). Continuous location tracking algorithm for moving position data. Journal of the Korean Data & Information Science Society , 19, 979-994.
  2. Kim, H. K. and Fang, Q. (2005). A note on balancedness of dominating set games. Journal of Combinatorial Optimization, 10, 303-310. https://doi.org/10.1007/s10878-005-4920-8
  3. Kim, H. K. and Fang, Q. (2006). Balancedness and concavity of fractional domination games. Bulletin of the Korean Mathematical Society, 43, 265-275. https://doi.org/10.4134/BKMS.2006.43.2.265
  4. Kim, H. K. and Fang, Q. (2006). Balancedness of integer domination games. Journal of the Korean Mathematical Society, 43, 297-309. https://doi.org/10.4134/JKMS.2006.43.2.297
  5. Kim, H. K. and Lee, D. S. (2007). Characterization of the core of integer total domination games. Journal of the Korean Data & Information Science Society , 18, 1115-1121.
  6. Haynes, T. W., Hedetniemi, S. T. and Slater, P. J. (1998). Fundamentals of domination in graphs, Marcel Dekker Inc.
  7. Velzen, B. van. (2004). Dominating set games. Operations Research Letters, 32, 565-573. https://doi.org/10.1016/j.orl.2004.02.004