{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:51Z","timestamp":1725664251277},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_143","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:19:08Z","timestamp":1330262348000},"page":"213-224","source":"Crossref","is-referenced-by-count":3,"title":["Optimal pattern matching on meshes"],"prefix":"10.1007","author":[{"given":"Bogdan S.","family":"Chlebus","sequence":"first","affiliation":[]},{"given":"Leszek","family":"Gasieniec","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"M.J. Atallah, F. Dehne, R. Miller, A. Rau-Chaplin, and J.-J. Tsay, Multisearch techniques for implementing data structures on a mesh-connected computer, in Proc. 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991, pp. 204\u2013214.","DOI":"10.1145\/113379.113398"},{"key":"17_CR2","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/S0019-9958(86)80046-8","volume":"69","author":"M.J. Atallah","year":"1986","unstructured":"M.J. Atallah, and S. Hambrush, Solving tree problems on a mesh-connected processor array, Information and Control 69 (1986) 168\u2013186.","journal-title":"Information and Control"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"M.J. Atallah, and S. Rao Kosaraju, Graph problems on a mesh-connected processor array, in Proc. 14th Annual ACM Symposium on Theory of Computing, 1982, pp. 345\u2013353.","DOI":"10.1145\/800070.802210"},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.1137\/0219072","volume":"19","author":"D. Breslauer","year":"1990","unstructured":"D. Breslauer, and Z. Galil, An optimal O(log log n) time parallel string matching algorithm, SIAM J. Computing 19 (1990) 1051\u20131058.","journal-title":"SIAM J. Computing"},{"key":"17_CR5","doi-asserted-by":"crossref","first-page":"856","DOI":"10.1137\/0221050","volume":"21","author":"D. Breslauer","year":"1992","unstructured":"D. Breslauer, and Z. Galil, A lower bound for parallel string matching, SIAM J. Computing 21 (1992) 856\u2013862.","journal-title":"SIAM J. Computing"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"B.S. Chlebus, M. Kaufmann, and J. Sibeyn, Deterministic permutation routing on meshes, in Proc. 5th IEEE Symp. on Parallel and Distributed Processing, 1993.","DOI":"10.1109\/SPDP.1993.395448"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"R. Cole, M. Crochemore, Z. Galil, L. Gasieniec, R.Hariharan, S. Muthukrishnan, K. Park and W. Rytter, Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions, in Proc. 34th Annual IEEE Symposium on Foundations of Computer Science, pp. 248\u2013258, 1993.","DOI":"10.1109\/SFCS.1993.366862"},{"key":"17_CR8","unstructured":"M. Crochemore, Z. Galil, L. Gasieniec, K. Park, and W. Rytter, Constant-time deterministic sampling and its applications, 1993, Manuscript."},{"key":"17_CR9","unstructured":"A. Czumaj, Z. Galil, L. Gasieniec, and W. Plandowski, From the CRCW-PRAM to the hypercube, via the CREW-PRAM and the EREW-PRAM (or In the Defense of the PRAM), 1993, manuscript."},{"key":"17_CR10","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/S0019-9958(85)80031-0","volume":"67","author":"Z. Galil","year":"1985","unstructured":"Z. Galil, Optimal parallel algorithms for string matching, Information and Control 67 (1985) 144\u2013157.","journal-title":"Information and Control"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"S. Hambrush, X. He, and R. Miller, Parallel algorithms for gray-scale image component labeling on a mesh-connected computer, in Proc. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992, pp. 100\u2013108.","DOI":"10.1145\/140901.140912"},{"key":"17_CR12","volume-title":"Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1992","unstructured":"J. J\u00e1J\u00e1, \u201dIntroduction to Parallel Algorithms\u201d, 1992, Addison-Wesley, Reading, Massachusetts."},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"C. Kaklamanis, and G. Persiano, Branch-and-bound and backtrack search on mesh-connected arrays of processors, in Proc. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992, pp. 118\u2013126.","DOI":"10.1145\/140901.140914"},{"key":"17_CR14","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"F.T. Leighton","year":"1992","unstructured":"F.T. Leighton, \u201dIntroduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes\u201d, 1992, Morgan Kaufmann, San Mateo, California."},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"F.T. Leighton, F. Makedon, and I.G. Tollis, A 2n \u2014 2 step algorithm for routing in an n \u00d7 n array with constant size queues, in Proc. 1st Annual ACM Symposium on Parallel Algorithms and Architectures, 1989, pp. 328\u2013335.","DOI":"10.1145\/72935.72970"},{"key":"17_CR16","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1109\/12.21120","volume":"38","author":"R. Miller","year":"1989","unstructured":"R. Miller, and Q.F. Stout, Mesh computer algorithms for computational geometry, IEEE Trans. Comp. 38 (1989) 321\u2013340.","journal-title":"IEEE Trans. Comp."},{"key":"17_CR17","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1137\/0209058","volume":"9","author":"D. Nassimi","year":"1980","unstructured":"D. Nassimi, and S. Sahni, Finding connected components and connected ones on a mesh-connected parallel computer, SIAM J. Computing 9 (1980) 744\u2013757.","journal-title":"SIAM J. Computing"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"C.P. Schnorr, and A. Shamir, An optimal sorting algorithm for mesh connected computers, in Proc. 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 255\u2013263.","DOI":"10.1145\/12130.12156"},{"key":"17_CR19","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0019-9958(85)80028-0","volume":"67","author":"U. Vishkin","year":"1985","unstructured":"U. Vishkin, Optimal parallel matching in strings, Information and Control 67 (1985) 91\u2013113.","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_143.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:13:55Z","timestamp":1605647635000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_143","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}