{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T19:57:29Z","timestamp":1721851049281},"reference-count":18,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2020,3,1]]},"DOI":"10.1587\/transinf.2019fcp0004","type":"journal-article","created":{"date-parts":[[2020,2,29]],"date-time":"2020-02-29T22:11:00Z","timestamp":1583014260000},"page":"500-505","source":"Crossref","is-referenced-by-count":5,"title":["Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles"],"prefix":"10.1587","volume":"E103.D","author":[{"given":"Chuzo","family":"IWAMOTO","sequence":"first","affiliation":[{"name":"Graduate School of Engineering, Hiroshima University"}]},{"given":"Tatsuaki","family":"IBUSUKI","sequence":"additional","affiliation":[{"name":"Graduate School of Engineering, Hiroshima University"}]}],"member":"532","reference":[{"key":"1","unstructured":"[1] http:\/\/nikoli.co.jp\/en\/puzzles\/kurotto.html"},{"key":"2","unstructured":"[2] http:\/\/nikoli.co.jp\/en\/puzzles\/juosan.html"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] A. Adcock, E.D. Demaine, M.L. Demaine, M.P. O'Brien, F. Reidl, F.S. Villaamil, and B.D. Sullivan, \u201cZig-zag numberlink is NP-complete,\u201d J. Inf. Process., vol.23, no.3, pp.239-245, 2015. 10.2197\/ipsjjip.23.239","DOI":"10.2197\/ipsjjip.23.239"},{"key":"4","unstructured":"[4] A. Allen and A. Williams, \u201cSto-Stone is NP-complete,\u201d Proc. 30th Canadian Conference on Computational Geometry, pp.28-34, 2018."},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] D. Andersson, \u201cHashiwokakero is NP-complete,\u201d Inf. Process. Lett., vol.109, no.19, pp.1145-1146, 2009. 10.1016\/j.ipl.2009.07.017","DOI":"10.1016\/j.ipl.2009.07.017"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] E.D. Demaine, Y. Okamoto, R. Uehara, and Y. Uno, \u201cComputational complexity and an integer programming model of Shakashaka,\u201d IEICE T. Fund. Electr., vol.E97-A, no.6, pp.1213-1219, 2014. 10.1587\/transfun.e97.a.1213","DOI":"10.1587\/transfun.E97.A.1213"},{"key":"7","unstructured":"[7] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, NY, 1979."},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] R.A. Hearn and E.D. Demaine, Games, Puzzles, and Computation, A K Peters Ltd., 2009.","DOI":"10.1201\/b10581"},{"key":"9","unstructured":"[9] A. Ishibashi, Y. Sato, and S. Iwata, \u201cNP-completeness of two pencil puzzles: Yajilin and Country Road,\u201d Utilitas Mathematica, vol.88, pp.237-246, 2012."},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] C. Iwamoto, \u201cYosenabe is NP-complete,\u201d J. Inf. Process., vol.22, no.1, pp.40-43, 2014. 10.2197\/ipsjjip.22.40","DOI":"10.2197\/ipsjjip.22.40"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] C. Iwamoto and M. Haruishi, \u201cComputational complexity of Usowan puzzles,\u201d IEICE Trans. Fundamentals, vol.E101-A, no.9, pp.1537-1540, 2018. 10.1587\/transfun.e101.a.1537","DOI":"10.1587\/transfun.E101.A.1537"},{"key":"12","unstructured":"[12] C. Iwamoto, M. Haruishi, and T. Ibusuki, \u201cHerugolf and Makaro are NP-complete,\u201d Proc. 9th International Conference on Fun with Algorithms, LIPICS, vol.100, pp.23:1-23:11, 2018."},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] C. Iwamoto and T. Ibusuki, \u201cDosun-Fuwari is NP-complete,\u201d J. Inf. Process., vol.26, pp.358-361, 2018. 10.2197\/ipsjjip.26.358","DOI":"10.2197\/ipsjjip.26.358"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] J. K\u00f6lker, \u201cKurodoko is NP-complete,\u201d J. Inf. Process., vol.20, no.3, pp.694-706, 2012. 10.2197\/ipsjjip.20.694","DOI":"10.2197\/ipsjjip.20.694"},{"key":"15","unstructured":"[15] D. Packer, S. White, and A. Williams, \u201cA paper on pencils: A pencil and paper puzzle-Pencils is NP-complete,\u201d Proc. 30th Canadian Conference on Computational Geometry, pp.35-41, 2018."},{"key":"16","unstructured":"[16] Y. Takenaga, S. Aoyagi, S. Iwata, and T. Kasai, \u201cShikaku and Ripple Effect are NP-complete,\u201d Congressus Numerantium, vol.216, pp.119-127, 2013."},{"key":"17","doi-asserted-by":"publisher","unstructured":"[17] A. Uejima and H. Suzuki, \u201cFillmat is NP-complete and ASP-complete,\u201d J. Inf. Process., vol.23, no.3, pp.310-316, 2015. 10.2197\/ipsjjip.23.310","DOI":"10.2197\/ipsjjip.23.310"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] A. Uejima, H. Suzuki, and A. Okada, \u201cThe complexity of generalized pipe link puzzles,\u201d J. Inf. Process., vol.25, pp.724-729, 2017. 10.2197\/ipsjjip.25.724","DOI":"10.2197\/ipsjjip.25.724"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E103.D\/3\/E103.D_2019FCP0004\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,7]],"date-time":"2020-03-07T03:26:57Z","timestamp":1583551617000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E103.D\/3\/E103.D_2019FCP0004\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,1]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2019fcp0004","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,1]]}}}