文献

J-GLOBAL ID：202202273703948353   整理番号：22A1077279

ファイブセルズとタイルペイントはNP完全である

Five Cells and Tilepaint are NP-Complete

著者 (2件)： IWAMOTO Chuzo (Graduate School of Advanced Science and Engineering, Hiroshima University) ,  IDE Tatsuya (Graduate School of Advanced Science and Engineering, Hiroshima University)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E105.D  号： 3  ページ： 508-516(J-STAGE)  発行年： 2022年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： ファイブセルズとタイルペイントは,Nikoliのペンシルパズルである。ファイブセルズとタイルペイントパズルの計算量を研究した。各パズルの与えられたインスタンスが解を持つかどうかを決定するのはNP完全であることを示した。(翻訳著者抄録)

シソーラス用語： *NP完全問題 ,  計算量理論 ,  ゲーム ,  充足可能性問題 ,  計算理論
準シソーラス用語： *NP完全 ,  パズル ,  多項式時間

著者キーワード (4件)： 5つの細胞 ,  タイル塗装 ,  ペンシルパズル ,  NP完全

分類 (1件)： 数値計算  (JE02000J)

引用文献 (25件)：

• [1] https://nikoli.co.jp/en/puzzles/five_cells.html
• [2] https://nikoli.co.jp/en/puzzles/tile_paint.html
• [3] A.B. Adcock, E.D. Demaine, M.L. Demaine, M.P. O'Brien, F. Reidl, F.S. Villaamil, and B.D. Sullivan, “Zig-zag numberlink is NP-complete,” J. Inf. Process., vol.23, no.3, pp.239-245, 2015. DOI: 10. 2197/ipsjjip.23.239 10.2197/ipsjjip.23.239
• [4] A. Adler, J. Bosboom, E.D. Demaine, M.L. Demaine, Q.C. Liu, and J. Lynch, “Tatamibari is NP-complete,” Proc. 10th International Conference on Fun with Algorithms, LIPICS, vol.157, pp.1:1-1:24, 2021. DOI: 10. 4230/LIPIcs.FUN.2021.1 10.4230/LIPIcs.FUN.2021.1
• [5] A. Allen and A. Williams, “Sto-Stone is NP-Complete,” Proc. 30th Canadian Conference on Computational Geometry, Winnipeg, Canada, pp.28-34, 2018.

タイトルに関連する用語 (3件)： タイル ,  ペイント ,  NP完全