{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,5]],"date-time":"2024-07-05T17:38:18Z","timestamp":1720201098032},"reference-count":23,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T00:00:00Z","timestamp":1761523200000},"content-version":"am","delay-in-days":665,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"publisher","award":["ANR-21-CE48-0022"],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2024,1]]},"DOI":"10.1016\/j.tcs.2023.114275","type":"journal-article","created":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T15:57:55Z","timestamp":1698163075000},"page":"114275","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Filling crosswords is very hard"],"prefix":"10.1016","volume":"982","author":[{"given":"Laurent","family":"Gourv\u00e8s","sequence":"first","affiliation":[]},{"given":"Ararat","family":"Harutyunyan","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Lampis","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-0864-9803","authenticated-orcid":false,"given":"Nikolaos","family":"Melissinos","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2023.114275_br0010","series-title":"Principles and Practice of Constraint Programming, 14th International Conference, CP 2008, Sydney, Australia, September 14-18, 2008. Proceedings","first-page":"550","article-title":"Crossword puzzles as a constraint problem","author":"Anbulagan","year":"2008"},{"issue":"2","key":"10.1016\/j.tcs.2023.114275_br0020","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1207\/s15328023top1002_10","article-title":"The crossword puzzle as a teaching tool","volume":"10","author":"Crossman","year":"1983","journal-title":"Teach. Psychol."},{"key":"10.1016\/j.tcs.2023.114275_br0030","series-title":"Parameterized Algorithms","author":"Cygan","year":"2015"},{"key":"10.1016\/j.tcs.2023.114275_br0040","series-title":"Fun with Algorithms - 6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012. Proceedings","first-page":"131","article-title":"On computer integrated rationalized crossword puzzle manufacturing","author":"Engel","year":"2012"},{"issue":"4","key":"10.1016\/j.tcs.2023.114275_br0050","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1137\/0205048","article-title":"On the complexity of timetable and multicommodity flow problems","volume":"5","author":"Even","year":"1976","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2023.114275_br0060","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/j.tcs.2023.114275_br0070","series-title":"Proceedings of the 8th National Conference on Artificial Intelligence. Boston, Massachusetts, USA, July 29 - August 3, 1990, 2 Volumes","first-page":"210","article-title":"Search lessons learned from crossword puzzles","author":"Ginsberg","year":"1990"},{"key":"10.1016\/j.tcs.2023.114275_br0080","series-title":"32nd International Symposium on Algorithms and Computation","first-page":"36:1","article-title":"Filling crosswords is very hard","author":"Gourv\u00e8s","year":"2021"},{"issue":"4","key":"10.1016\/j.tcs.2023.114275_br0090","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","article-title":"An n5\/2 algorithm for maximum matchings in bipartite graphs","volume":"2","author":"Hopcroft","year":"1973","journal-title":"SIAM J. Comput."},{"issue":"5","key":"10.1016\/j.tcs.2023.114275_br0100","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1016\/j.orl.2008.05.004","article-title":"Multigraph realizations of degree sequences: maximization is easy, minimization is hard","volume":"36","author":"Hulett","year":"2008","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"10.1016\/j.tcs.2023.114275_br0110","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","article-title":"Which problems have strongly exponential complexity?","volume":"63","author":"Impagliazzo","year":"2001","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10.1016\/j.tcs.2023.114275_br0120","first-page":"7","article-title":"Maximum matching of given weight in complete and complete bipartite graphs","volume":"23","author":"Karzanov","year":"1987","journal-title":"Kibernetika"},{"issue":"3","key":"10.1016\/j.tcs.2023.114275_br0130","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","article-title":"Vertex cover might be hard to approximate to within 2-epsilon","volume":"74","author":"Khot","year":"2008","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"10.1016\/j.tcs.2023.114275_br0140","first-page":"284","article-title":"Scrabble is PSPACE-complete","volume":"23","author":"Lampis","year":"2015","journal-title":"J. Inf. Process."},{"key":"10.1016\/j.tcs.2023.114275_br0150","series-title":"Proceedings of the Sixteenth National Conference on Artificial Intelligence and Eleventh Conference on Innovative Applications of Artificial Intelligence","first-page":"914","article-title":"Solving crosswords with PROVERB","author":"Littman","year":"1999"},{"key":"10.1016\/j.tcs.2023.114275_br0160","unstructured":"T\u00e9l\u00e9 Magazine, Publications Grand Public."},{"key":"10.1016\/j.tcs.2023.114275_br0170","series-title":"Proceedings of Expert Systems 97: Research and Development in Expert Systems XIV","first-page":"159","article-title":"Constructing crossword grids: use of heuristics vs constraints","author":"Meehan","year":"1997"},{"key":"10.1016\/j.tcs.2023.114275_br0180","series-title":"21st Annual Symposium on Foundations of Computer Science","first-page":"17","article-title":"An o(sqrt(|v|) |e|) algorithm for finding maximum matching in general graphs","author":"Micali","year":"1980"},{"issue":"1","key":"10.1016\/j.tcs.2023.114275_br0190","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","article-title":"Matching is as easy as matrix inversion","volume":"7","author":"Mulmuley","year":"1987","journal-title":"Combinatorica"},{"issue":"2","key":"10.1016\/j.tcs.2023.114275_br0200","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/322307.322309","article-title":"The complexity of restricted spanning tree problems","volume":"29","author":"Papadimitriou","year":"1982","journal-title":"J. ACM"},{"issue":"6","key":"10.1016\/j.tcs.2023.114275_br0210","doi-asserted-by":"crossref","first-page":"1006","DOI":"10.1017\/S1355617711001111","article-title":"Association of crossword puzzle participation with memory decline in persons who develop dementia","volume":"17","author":"Pillai","year":"2011","journal-title":"J. Int. Neuropsychol. Soc."},{"issue":"3","key":"10.1016\/j.tcs.2023.114275_br0220","doi-asserted-by":"crossref","DOI":"10.1142\/S0218213012500145","article-title":"Automatic generation of crossword puzzles","volume":"21","author":"Rigutini","year":"2012","journal-title":"Int. J. Artif. Intell. Tools"},{"key":"10.1016\/j.tcs.2023.114275_br0230","series-title":"IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence","first-page":"649","article-title":"Nested rollout policy adaptation for Monte Carlo tree search","author":"Rosin","year":"2011"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397523005881?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397523005881?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,6,18]],"date-time":"2024-06-18T17:59:08Z","timestamp":1718733548000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397523005881"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1]]},"references-count":23,"alternative-id":["S0304397523005881"],"URL":"http:\/\/dx.doi.org\/10.1016\/j.tcs.2023.114275","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2024,1]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Filling crosswords is very hard","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2023.114275","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2023 Elsevier B.V. All rights reserved.","name":"copyright","label":"Copyright"}],"article-number":"114275"}}
