WEKO3
アイテム
Selected Slither Link Variants are NP-complete
https://ipsj.ixsq.nii.ac.jp/records/82608
https://ipsj.ixsq.nii.ac.jp/records/82608a2a48934-f9c8-46d4-a9f0-1ff2b84dde5c
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL5306011 (554.0 kB)
|
Copyright (c) 2012 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-06-15 | |||||||
| タイトル | ||||||||
| タイトル | Selected Slither Link Variants are NP-complete | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Selected Slither Link Variants are NP-complete | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | [特集：パズルの数理] puzzles, combinatorics, computational complexity, NP-completeness | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| Department of Computer Science, Aarhus University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, Aarhus University | ||||||||
| 著者名 |
Jonas, Kolker
× Jonas, Kolker
|
|||||||
| 著者名(英) |
Jonas, Kolker
× Jonas, Kolker
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In a Slither Link puzzle, the player must draw a cycle in a planar graph, such that the number of edges incident to a set of clue faces equals the set of given clue values. We show that for a number of commonly played graph classes, the Slither Link puzzle is NP-complete. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.20(2012) No.3 (online) DOI http://dx.doi.org/10.2197/ipsjjip.20.709 ------------------------------ |
|||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In a Slither Link puzzle, the player must draw a cycle in a planar graph, such that the number of edges incident to a set of clue faces equals the set of given clue values. We show that for a number of commonly played graph classes, the Slither Link puzzle is NP-complete. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.20(2012) No.3 (online) DOI http://dx.doi.org/10.2197/ipsjjip.20.709 ------------------------------ |
|||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116647 | |||||||
| 書誌情報 |
情報処理学会論文誌 巻 53, 号 6, 発行日 2012-06-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7764 | |||||||
