{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T18:52:40Z","timestamp":1648839160434},"reference-count":29,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,3,1]],"date-time":"2001-03-01T00:00:00Z","timestamp":983404800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4521,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2001,3]]},"DOI":"10.1016\/s0304-3975(99)00153-x","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T21:51:54Z","timestamp":1027633914000},"page":"51-62","source":"Crossref","is-referenced-by-count":0,"title":["Approximation algorithms for maximum two-dimensional pattern matching"],"prefix":"10.1016","volume":"255","author":[{"given":"Srinivasa","family":"R. Arikati","sequence":"first","affiliation":[]},{"given":"Anders","family":"Dessmark","sequence":"additional","affiliation":[]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[]},{"given":"Madhav","family":"V. Marathe","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(99)00153-X_BIB1","unstructured":"A. Amir, M. Farach, Efficient 2-dimensional approximate matching of non-rectangular figures, Proc. 2nd Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), 1992, pp. 212\u2013223."},{"key":"10.1016\/S0304-3975(99)00153-X_BIB2","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1137\/S0097539792226321","article-title":"An alphabet-independent approach to two-dimensional matching","volume":"23","author":"Amir","year":"1994","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00153-X_BIB3","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1137\/0207043","article-title":"A technique for extending rapid exact-match string matching to arrays of more than one dimension","volume":"7","author":"Baker","year":"1978","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00153-X_BIB4","doi-asserted-by":"crossref","unstructured":"B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs, 24th IEEE Symp. on Foundations of Computer Science (FOCS), 1983, pp. 265\u2013273. (Journal version in J. ACM (41)(1) (1994) 153\u2013180.)","DOI":"10.1145\/174644.174650"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB5","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1006\/jcss.1996.0003","article-title":"A theory of parameterized pattern matching","volume":"52","author":"Baker","year":"1996","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(99)00153-X_BIB6","doi-asserted-by":"crossref","unstructured":"R.S. Bird, Two-dimensional pattern matching, Inform. Process. Lett. (6) (1977) 168\u2013170.","DOI":"10.1016\/0020-0190(77)90017-5"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB7","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender, Dynamic programming on graphs of bounded treewidth, Proc. 15th Internat. Colloquium on Automata Languages and Programming (ICALP), Lecture Notes in Computer Science, Vol. 317, 1988, pp. 105\u2013118.","DOI":"10.1007\/3-540-19488-6_110"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB8","unstructured":"CANDID Project, Los Alamos National Laboratory, 1993."},{"key":"10.1016\/S0304-3975(99)00153-X_BIB9","series-title":"Text Algorithms","author":"Crochemore","year":"1994"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB10","doi-asserted-by":"crossref","unstructured":"A. Czumaj, Z. Galil, L. Gasieniec, K. Park, W. Plandowski, Work-time-optimal parallel algorithms for string problems, 27th ACM Symp. on Theory of Computing (STOC), 1995, pp. 713\u2013722.","DOI":"10.1145\/225058.225289"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB11","doi-asserted-by":"crossref","unstructured":"D. Eppstein, G.L. Miller, S.H. Teng, A deterministic linear time algorithm for geometric separators and its application, 9th ACM Symp. on Computational Geometry, 1993, pp. 99\u2013108.","DOI":"10.1145\/160985.161005"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB12","doi-asserted-by":"crossref","unstructured":"T. Feder, D. Greene, Optimal algorithms for approximate clustering, 20th ACM Symp. on Theory Of Computing (STOC), 1988, pp. 434\u2013444.","DOI":"10.1145\/62212.62255"},{"issue":"3","key":"10.1016\/S0304-3975(99)00153-X_BIB13","first-page":"133","volume":"12","author":"Fowler","year":"1981","journal-title":"Optimal packing and covering in the plane are NP-complete Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(99)00153-X_BIB14","series-title":"Handbook of Algorithms and Data Structures","author":"Gonnet","year":"1991"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB15","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","article-title":"The intersection graphs of subtrees in trees are exactly the chordal graphs","volume":"16","author":"Gavril","year":"1974","journal-title":"J. Combin. Theory B"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB16","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","article-title":"Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph","volume":"51","author":"Gavril","year":"1972","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00153-X_BIB17","unstructured":"M.M. Halld\u00f3rsson, Approximating discrete collections via local improvement, Proc. 6th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), 1995, pp. 160\u2013169."},{"key":"10.1016\/S0304-3975(99)00153-X_BIB18","series-title":"Graph Theory","author":"Harary","year":"1979"},{"issue":"1","key":"10.1016\/S0304-3975(99)00153-X_BIB19","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","article-title":"Approximation schemes for covering and packing problems in image processing and VLSI","volume":"32","author":"Hochbaum","year":"1985","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB20","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0196-6774(87)90012-5","article-title":"Fast approximation algorithms for a nonconvex covering problem","volume":"8","author":"Hochbaum","year":"1987","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB21","doi-asserted-by":"crossref","unstructured":"R. Idury, A. Sch\u00e4ffer, Multiple matching of rectangular figures, Proc. 25th ACM Symp. Theory of Computing, 1993, pp. 81\u201389.","DOI":"10.1145\/167088.167116"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB22","unstructured":"P.M. Kelly, T.M. Cannon, D.R. Hush, Query by image example: the CANDID approach, SPIE Vol. 2420 Storage and Retrieval for Image and Video Databases III, 1995, pp. 238\u2013248."},{"key":"10.1016\/S0304-3975(99)00153-X_BIB23","doi-asserted-by":"crossref","unstructured":"P.M. Kelly, T.M. Cannon, CANDID: comparison algorithm for navigating digital image databases, In Proc. of the 7th Internat. Working Conf. on Scientific and Statistical Database Management, Charlottesville, VA, September, 1994, pp. 252\u2013258.","DOI":"10.1109\/SSDM.1994.336943"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB24","doi-asserted-by":"crossref","unstructured":"S.R. Kosaraju, Faster algorithms for the construction of parameterized suffix trees, 36th IEEE Symp. on Foundations of Computer Science (FOCS), 1995, pp. 631\u2013637.","DOI":"10.1109\/SFCS.1995.492664"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB25","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","article-title":"Applications of a planar separator theorem","volume":"9","author":"Lipton","year":"1980","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00153-X_BIB26","doi-asserted-by":"crossref","unstructured":"G.L. Miller, S.-H. Teng, S.A. Vavasis, A unified geometric approach to graph separators, Proc. of the 32nd IEEE Symp. on Foundations of Computer Science, 1991, pp. 538\u2013547.","DOI":"10.1109\/SFCS.1991.185417"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB27","series-title":"Computational Geometry","author":"Preparata","year":"1985"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB28","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","article-title":"Graph Minors II. Algorithmic aspects of tree-width","volume":"7","author":"Robertson","year":"1986","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(99)00153-X_BIB29","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","article-title":"Algorithmic aspects of vertex elimination on graphs","volume":"5","author":"Rose","year":"1976","journal-title":"SIAM J. Comput."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439759900153X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439759900153X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,28]],"date-time":"2020-01-28T18:14:08Z","timestamp":1580235248000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S030439759900153X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,3]]},"references-count":29,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,3]]}},"alternative-id":["S030439759900153X"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(99)00153-x","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2001,3]]}}}