{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:25Z","timestamp":1725664225261},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540612582"},{"type":"electronic","value":"9783540683902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61258-0_25","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:21:02Z","timestamp":1330273262000},"page":"348-360","source":"Crossref","is-referenced-by-count":1,"title":["Approximation algorithms for maximum two-dimensional pattern matching"],"prefix":"10.1007","author":[{"given":"Srinivasa R.","family":"Arikati","sequence":"first","affiliation":[]},{"given":"Anders","family":"Dessmark","sequence":"additional","affiliation":[]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[]},{"given":"Madhav","family":"Marathe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"25_CR1","unstructured":"A. Amir, and M. Farach, \u201cEfficient 2-dimensional Approximate Matching of Non-Rectangular Figures,\u201d Proc. 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1992, pp. 212\u2013223."},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"A. Amir, G. Benson, G. Benson and M. Farach. An Alphabet-independent Approach to Two-Dimensional Matching. Proc. 24th ACM Symposium on Theory of Computing, 1992, pp. 59\u201368. Journal version to appear in SIAM J. Computing.","DOI":"10.1145\/129712.129719"},{"key":"25_CR3","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1137\/0207043","volume":"No. 7","author":"T. P. Baker","year":"1978","unstructured":"T. P. Baker. A technique for extending rapid exact-match string matching to arrays of more than one dimension. SIAM J. Computing, No. 7, 1978, pp. 533\u2013541.","journal-title":"SIAM J. Computing"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"B.S. Baker. \u201cApproximation Algorithms for NP-complete Problems on Planar Graphs,\u201d 24th IEEE Symposium on Foundations of Computer Science (FOCS), 1983, pp 265\u2013273. (Journal version in J. ACM, Vol. 41, No. 1, 1994, pp. 153\u2013180.)","DOI":"10.1145\/174644.174650"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"B. Baker, \u201cA Theory of Parameterized Pattern Matching: Algorithms and Applications,\u201d Proc. 25th ACM Symposium on Theory of Computing, 1993, pp. 71\u201380. Journal version to appear in Journal of Computer and System Sciences (JCSS).","DOI":"10.1145\/167088.167115"},{"key":"25_CR6","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0020-0190(77)90017-5","volume":"No. 6","author":"R. S. Bird","year":"1977","unstructured":"R. S. Bird. \u201cTwo-dimensional pattern matching,\u201d Information Processing Letters No. 6, 1977, pp. 168\u2013170.","journal-title":"Information Processing Letters"},{"key":"25_CR7","first-page":"105","volume":"317","author":"H. L. Bodlaender","year":"1988","unstructured":"H. L. Bodlaender, \u201cDynamic programming on graphs of bounded treewidth,\u201d Proc. 15th International Colloquium on Automata Languages and Programming (ICALP), LNCS Vol. 317, 1988, pp. 105\u2013118.","journal-title":"LNCS"},{"key":"25_CR8","unstructured":"\u201cCANDID Project,\u201d Los Alamos National Laboratory, 1993."},{"key":"25_CR9","volume-title":"Text Algorithms","author":"M. Crochemore","year":"1994","unstructured":"M. Crochemore and W. Rytter. Text Algorithms, Oxford University Press, New York, 1994."},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"A. Czumaj, Z. Galil, L. Gasieniec, K. Park and W. Plandowski, \u201cWork-Time-Optimal Parallel Algorithms for String Problems,\u201d 27th ACM Symposium on Theory Of Computing (STOC), pp. 713\u2013722, 1995.","DOI":"10.1145\/225058.225289"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"D. Eppstein, G.L. Miller, S.H. Teng. \u201cA Deterministic Linear Time Algorithm for Geometric Separators and its Application,\u201d 9th ACM Symposium on Computational Geometry, pp 99\u2013108, 1993.","DOI":"10.1145\/160985.161005"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"M. Farach and M. Thorup, \u201cString Matching in Lempel-Ziv Compressed Strings,\u201d 27th ACM Symposium on Theory Of Computing (STOC), pp. 703\u2013712, 1995.","DOI":"10.1145\/225058.225288"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"T. Feder and D. Greene. \u201cOptimal Algorithms for Approximate Clustering\u201d, 20th ACM Symposium on Theory Of Computing (STOC), pp. 434\u2013444, 1988.","DOI":"10.1145\/62212.62255"},{"issue":"No.3","key":"25_CR14","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R.J. Fowler","year":"1981","unstructured":"R.J. Fowler, M.S. Paterson and S.L. Tanimoto. \u201cOptimal Packing and Covering in the Plane are NP-Complete,\u201d Information Processing Letters, Vol 12, No.3, June 1981, pp. 133\u2013137.","journal-title":"Information Processing Letters"},{"key":"25_CR15","volume-title":"Handbook of Algorithms and Data Structures","author":"G.H. Gonnet","year":"1991","unstructured":"G.H. Gonnet and R. Baeza Yates, Handbook of Algorithms and Data Structures, Addison-Wesley, Reading, MA, 1991."},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"F. Gavril, \u201cThe intersection graphs of subtrees in trees are exactly the chordal graphs,\u201d J. Combin. Theory B, 16, 1974, pp. 47\u201356.","journal-title":"J. Combin. Theory B"},{"key":"25_CR17","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"F. Gavril, \u201cAlgorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph,\u201d SIAM J. Computing, 1, 1972, pp. 180\u2013187.","journal-title":"SIAM J. Computing"},{"key":"25_CR18","unstructured":"M.M. Halld\u00f3rsson, \u201cApproximating Discrete Collections via Local Improvement,\u201d Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1995, pp. 160\u2013169"},{"key":"25_CR19","volume-title":"Graph Theory","author":"F. Harary","year":"1979","unstructured":"F. Harary, Graph Theory, Addison-Wesley, Reading, Massachusetts, 1979."},{"issue":"No.1","key":"25_CR20","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"D.S. Hochbaum and W. Maass, \u201cApproximation Schemes for Covering and Packing Problems in Image Processing and VLSI,\u201d J. ACM, Vol 32, No. 1, 1985, pp 130\u2013136.","journal-title":"J. ACM"},{"key":"25_CR21","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0196-6774(87)90012-5","volume":"8","author":"D.S. Hochbaum","year":"1987","unstructured":"D.S. Hochbaum and W. Maass, \u201cFast Approximation Algorithms for a Nonconvex Covering Problem,\u201d Journal of Algorithms, Vol. 8, 1987, pp. 305\u2013323.","journal-title":"Journal of Algorithms"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"R. Idury and A. Sch\u00e4ffer, \u201cMultiple Matching of Rectangular Figures,\u201d Proc. 25th ACM Symposium on Theory of Computing, 1993, pp. 81\u201389.","DOI":"10.1145\/167088.167116"},{"key":"25_CR23","unstructured":"P.M. Kelly, T.M. Cannon, and D.R. Hush, \u201cQuery by image example: the CANDID approach,\u201d SPIE Vol. 2420 Storage and Retrieval for Image and Video Databases III, pages 238\u2013248, 1995."},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"P.M. Kelly and T.M. Cannon, \u201cCANDID: Comparison Algorithm for Navigating Digital Image Databases,\u201d In Proc. of the 7th International Working Conference on Scientific and Statistical Database Management, pages 252\u2013258. Charlottesville, VA, Sept., 1994.","DOI":"10.1109\/SSDM.1994.336943"},{"key":"25_CR25","doi-asserted-by":"crossref","unstructured":"S. R. Kosaraju, \u201cFaster Algorithms for the Construction of Parameterized Suffix Trees,\u201d 36th IEEE Symposium on Foundations of Computer Science (FOCS), 1995, pp 631\u2013637.","DOI":"10.1109\/SFCS.1995.492664"},{"key":"25_CR26","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"R. J. Lipton and R. E. Tarjan, \u201cApplications of a planar separator theorem,\u201d SIAM J. Computing, 9, 1980, pp. 615\u2013627.","journal-title":"SIAM J. Computing"},{"key":"25_CR27","doi-asserted-by":"crossref","unstructured":"G.L. Miller, S.-H. Teng and S.A. Vavasis, \u201cA Unified Geometric Approach to Graph Separators,\u201d Proc. of the 32nd IEEE Symposium on Foundations of Computer Science, 1991, pp. 538\u2013547.","DOI":"10.1109\/SFCS.1991.185417"},{"key":"25_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos, Computational Geometry, Springer Verlag, New York, 1985."},{"key":"25_CR29","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"No. 7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P. Seymour, \u201cGraph Minors II. Algorithmic aspects of treewidth,\u201d J. Algorithms, No. 7 (1986), 309\u2013322.","journal-title":"J. Algorithms"},{"key":"25_CR30","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D. J. Rose","year":"1976","unstructured":"D. J. Rose, R. E. Tarjan and G. S. Lueker, \u201cAlgorithmic aspects of vertex elimination on graphs,\u201d SIAM J. Computing, 5, 1976, pp. 266\u2013283.","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61258-0_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:04:44Z","timestamp":1605629084000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61258-0_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540612582","9783540683902"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-61258-0_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}