Voronoi game on graphs and its complexity

• Teramoto Sachio

• Uehara Ryuhei

Bibliographic Information

Other Title

• グラフ上のボロノイゲームとその困難性

Abstract

The Voronoi game is a two-person game which is a model for a competitive facility location. The game is done on a continuous domain, and only two special cases (1-dimensional case and 1-round case) are well investigated. We introduce the discrete Voronoi game of which the game arena is given as a graph. We first show the best strategy when the game arena is a large complete k-ary tree. We also show that the discrete Voronoi game is NP-hard on a given general graph, even in 1-round case.　：　ボロノイゲームは競争施設配置問題をモデル化した二人ゲームである。これまで、ボロノイゲームは連続領域の上で定義され、二つの特別な場合（１次元の場合と１-ラウンドの場合）についてのみ良く調べられている。本論文では、離散的なボロノイゲームを導入する。つまり、与えられたグラフ上でのボロノイゲームを考える。はじめに、与えられたグラフが十分大きな完全ｋ分水である場合の最良の戦略を示す。また、一般のグラフ上の１-ラウンド離散ボロノイゲームに対するNP-困難性を示す。

identifier:09196072

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/3275

Journal

• 情報処理学会研究報告 : アルゴリズム研究会報告

  情報処理学会研究報告 : アルゴリズム研究会報告 2006 (7), 9-16, 2006-01

  情報処理学会

Keywords

• Voronoi Game
• NP-completeness
• ボロノイゲーム
• NP‐完全性

Details

• CRID: 1050564287489454976
• NII Article ID: 110004075873
• NII Book ID: AN10539294
• ISSN: 09196072
• NDL BIB ID: 7808775
• Web Site: http://hdl.handle.net/10119/3275
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I7808775
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • NDL
  • CiNii Articles