{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:12:10Z","timestamp":1725541930174},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112652"},{"type":"electronic","value":"9783642112669"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11266-9_13","type":"book-chapter","created":{"date-parts":[[2009,12,7]],"date-time":"2009-12-07T09:04:58Z","timestamp":1260176698000},"page":"153-164","source":"Crossref","is-referenced-by-count":4,"title":["Approximability of Edge Matching Puzzles"],"prefix":"10.1007","author":[{"given":"Antonios","family":"Antoniadis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s00373-007-0713-4","volume":"23","author":"E.D. Demaine","year":"2007","unstructured":"Demaine, E.D., Demaine, M.L.: Jigsaw Puzzles, Edge Matching, and Polyonymo Packing: Connections and Complexity. Graphs and Combinatorics\u00a023, 195\u2013208 (2007)","journal-title":"Graphs and Combinatorics"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Berger, R.: The Undecidability of the Domino Problem. Memoirs of the American Mathematical Society 66 (1966)","DOI":"10.1090\/memo\/0066"},{"key":"13_CR3","first-page":"257","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S., Papadimitriou, C.H.: Computers and Intractability: A Guide to the Theory of NP-completeness, p. 257. W.H.\u00a0Freeman & Co., New York (1979)"},{"key":"13_CR4","first-page":"354","volume-title":"Proceedings 2nd\u00a0Frege Conference","author":"M.P.W. Savelsberg","year":"1984","unstructured":"Savelsberg, M.P.W., van Emde Boas, P.: BOUNDED TILING, an Alternative to SATISFIABILITY? In: Proceedings 2nd\u00a0Frege Conference, vol.\u00a020, pp. 354\u2013363. Akademie Verlag, Schwerin (1984)"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1016\/0022-0000(86)90036-X","volume":"32","author":"B.S. Chlebus","year":"1986","unstructured":"Chlebus, B.S.: Domino-Tiling Games. Journal of Computer and System Sciences\u00a032, 374\u2013392 (1986)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR6","first-page":"36","volume":"3","author":"T. Benoist","year":"2008","unstructured":"Benoist, T., Bourreau, E.: Fast Global Filtering for Eternity II. Constraint Programming Letters\u00a03, 36\u201349 (2008)","journal-title":"Constraint Programming Letters"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1007\/978-3-540-85958-1_42","volume-title":"Principles and Practice of Constraint Programming","author":"C. Ans\u00f3tegui","year":"2008","unstructured":"Ans\u00f3tegui, C., B\u00e9jar, R., Fern\u00e1ndez, C., Mateau, C.: Edge Matching Puzzles as Hard SAT\/CSP Benchmarks. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol.\u00a05202, pp. 560\u2013565. Springer, Heidelberg (2008)"},{"key":"13_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. Springer, Heidelberg (1999)"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, Approximation, and Complexity Classes. Journal of Computer and System Sciences\u00a043, 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"Kann, V.: Maximum Bounded 3-Dimensional Matching is MAX SNP-Complete. Information Processing Letters\u00a037, 27\u201335 (1991)","journal-title":"Information Processing Letters"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Chleb\u00eck, M., Chleb\u00eckov\u00e0, J.: Approximation Hardness for Small Occurrence Instances of NP-hard Problems. In: Petreschi, R., Persiano, G., Silvestri, R. (eds.) CIAC 2003. LNCS, vol.\u00a02653. Springer, Heidelberg (2003); (also ECCC Report) (2002)","DOI":"10.1007\/3-540-44849-7_21"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Chleb\u00eck, M., Chleb\u00eckov\u00e0, J.: Inapproximability Results for Bounded Variants of Optimization Problems. In: Proocedings of FCT\u00a02003: the 14th\u00a0International Symposium on Fundamentals of Computation Theory (2003)","DOI":"10.1007\/978-3-540-45077-1_4"},{"key":"13_CR13","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2010: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11266-9_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T04:44:44Z","timestamp":1558673084000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11266-9_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642112652","9783642112669"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11266-9_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}