{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:14:14Z","timestamp":1726409654763},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734369"},{"type":"electronic","value":"9783540734376"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73437-6_6","type":"book-chapter","created":{"date-parts":[[2007,8,13]],"date-time":"2007-08-13T13:36:44Z","timestamp":1187012204000},"page":"28-39","source":"Crossref","is-referenced-by-count":2,"title":["Finding Witnesses by Peeling"],"prefix":"10.1007","author":[{"given":"Yonatan","family":"Aumann","sequence":"first","affiliation":[]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[]},{"given":"Noa","family":"Lewenstein","sequence":"additional","affiliation":[]},{"given":"Dekel","family":"Tsur","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"6_CR1","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K. Abrahamson","year":"1987","unstructured":"Abrahamson, K.: Generalized string matching. SIAM J. on Computing\u00a016(6), 1039\u20131051 (1987)","journal-title":"SIAM J. on Computing"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Galil, Z., Margalit, O., Naor, M.: Witnesses for boolean matrix multiplication and for shortest paths. In: Symposium on Foundations of Computer Science (FOCS), pp. 417\u2013426 (1992)","DOI":"10.1109\/SFCS.1992.267748"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/BF01940874","volume":"16","author":"N. Alon","year":"1996","unstructured":"Alon, N., Naor, M.: Derandomization, witnesses for boolean matrix multiplication and construction of perfect hash functions. Algorithmica\u00a016, 434\u2013449 (1996)","journal-title":"Algorithmica"},{"issue":"1","key":"6_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1995.1047","volume":"118","author":"A. Amir","year":"1995","unstructured":"Amir, A., Farach, M.: Efficient 2-dimensional approximate matching of half-rectangular figures. Information and Computation\u00a0118(1), 1\u201311 (1995)","journal-title":"Information and Computation"},{"issue":"2","key":"6_CR5","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0196-6774(03)00097-X","volume":"50","author":"A. Amir","year":"2004","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. J. of Algorithms\u00a050(2), 257\u2013275 (2004)","journal-title":"J. of Algorithms"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Brito, C., Gafni, E., Vaya, S.: An information theoretic lower bound for broadcasting in radio networks. In: Proc. 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 534\u2013546 (2004)","DOI":"10.1007\/978-3-540-24749-4_47"},{"issue":"1","key":"6_CR7","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s446-002-8028-1","volume":"15","author":"B.S. Chlebus","year":"2002","unstructured":"Chlebus, B.S., Gasieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in ad hoc radio networks. Distributed Computing\u00a015(1), 27\u201338 (2002)","journal-title":"Distributed Computing"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Clementi, A.E.F., Monti, A., Silvestri, R.: Selective families, superimposed codes, and broadcasting on unknown radio networks. In: Proc. 13th Symposium on Discrete Algorithms(SODA), pp. 709\u2013718 (2001)","DOI":"10.1145\/383962.384040"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0020-0190(98)00096-9","volume":"67","author":"P. Damaschke","year":"1998","unstructured":"Damaschke, P.: Randomized group testing for mutually obscuring defectives. Information Processing Letters\u00a067, 131\u2013135 (1998)","journal-title":"Information Processing Letters"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Du, D.Z., Hwang, F.K.: Combinatorial group testing and its applications. World Scientific (2000)","DOI":"10.1142\/9789812798107"},{"issue":"4","key":"6_CR11","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/8307.8309","volume":"17","author":"Z. Galil","year":"1986","unstructured":"Galil, Z., Giancarlo, R.: Improved string matching with k mismatches. SIGACT News.\u00a017(4), 52\u201354 (1986)","journal-title":"SIGACT News"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Interpolation of symmetric functions and a new type of combinatorial design. In: Proc. of Symposium on Theory of Computing (STOC), pp. 736\u2013740 (1999)","DOI":"10.1145\/301250.301445"},{"key":"6_CR13","unstructured":"Indyk, P.: Explicit constructions of selectors and related combinatorial structures, with applications. In: Proc. 13th Symposium on Discrete Algorithms (SODA), pp. 697\u2013704 (2002)"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comp.\u00a06, 323\u2013350 (1977)","journal-title":"SIAM J. Comp."},{"issue":"2","key":"6_CR15","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1109\/TIT.1985.1057020","volume":"31","author":"J. Koml\u00f3s","year":"1985","unstructured":"Koml\u00f3s, J., Greenberg, A.G.: An asymptotically nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Trans. on Information Theory\u00a031(2), 302\u2013306 (1985)","journal-title":"IEEE Trans. on Information Theory"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"G.M. Landau","year":"1986","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching with k mismatches. Theoretical Computer Science\u00a043, 239\u2013249 (1986)","journal-title":"Theoretical Computer Science"},{"key":"6_CR17","unstructured":"Muthukrishnan, S.: Personal communication"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/3-540-60044-2_50","volume-title":"Combinatorial Pattern Matching","author":"S. Muthukrishnan","year":"1995","unstructured":"Muthukrishnan, S.: New results and open problems related to non-standard stringology. In: Galil, Z., Ukkonen, E. (eds.) Combinatorial Pattern Matching. LNCS, vol.\u00a0937, pp. 298\u2013317. Springer, Heidelberg (1995)"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R. Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. of Computer and System Sciences\u00a051, 400\u2013403 (1995)","journal-title":"J. of Computer and System Sciences"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Ta-Shma, A., Umans, C., Zuckerman, D.: Loss-less condensers, unbalanced expanders, and extractors. In: Proc. 33th Symposium on the Theory of Computing (STOC), pp. 143\u2013152 (2001)","DOI":"10.1145\/380752.380790"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73437-6_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:12:14Z","timestamp":1619503934000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73437-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734369","9783540734376"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73437-6_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}