WEKO3
-
RootNode
アイテム
スリザーリンクのNP完全性について
https://ipsj.ixsq.nii.ac.jp/records/32081
https://ipsj.ixsq.nii.ac.jp/records/320815280f006-05b0-429a-b3ea-cb61ae2767f6
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL00074004.pdf (501.6 kB)
|
Copyright (c) 2000 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2000-09-21 | |||||||
| タイトル | ||||||||
| タイトル | スリザーリンクのNP完全性について | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | On the NP - completeness of the Slither Link Puzzle | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 東京大学大学院理学系研究科情報科学専攻 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Science, Graduate School of Science, The University of Tokyo | ||||||||
| 著者名 |
八登, 崇之
× 八登, 崇之
|
|||||||
| 著者名(英) |
Takayuki, Yato
× Takayuki, Yato
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 現在多くの人に遊ばれているゲームやパズルの多くについて，その計算量が解析されている．本稿では，パズルの一種であるスリザーリンクについて，解があるかを判定する問題のNP完全性を制限されたハミルトン閉路問題からの多項式時間還元を用いて証明する．また，スリザーリンクの別解問題（Another Solution Problem，1つ解が与えられた時に他に解があるかを判定する問題）について考察し，そのNP完全性の証明の指針を示す． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | For many of the widely played games and puzzles, their computational complexities have been analyzed. In this paper, we consider a sort of puzzle "Slither Link" and prove that the problem which determines whether or not a given instance of puzzle has any solutions is NP-complete, by using a polynomial time reduction from the Hamilton Path Problem with respect to restricted graphs. In addition we consider Another Solution Problem for the puzzle, the problem which determines, for a given instance and its solution, whether there is another solution for the instance. We provide a strategy to prove its NP-completeness. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 2000, 号 84(2000-AL-074), p. 25-31, 発行日 2000-09-21 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
