{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T19:21:11Z","timestamp":1777317671906,"version":"3.51.4"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,11,27]],"date-time":"2014-11-27T00:00:00Z","timestamp":1417046400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1007\/s00453-014-9957-6","type":"journal-article","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T10:24:22Z","timestamp":1417515862000},"page":"571-588","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Binary Jumbled Pattern Matching on Trees and Tree-Like Structures"],"prefix":"10.1007","volume":"73","author":[{"given":"Travis","family":"Gagie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gad M.","family":"Landau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,27]]},"reference":[{"issue":"4","key":"9957_CR1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0020-0190(97)00170-1","volume":"64","author":"S Alstrup","year":"1997","unstructured":"Alstrup, S., Secher, J., Sporkn, M.: Optimal on-line decremental connectivity in trees. Inf. Process. Lett. 64(4), 161\u2013164 (1997)","journal-title":"Inf. Process. Lett."},{"key":"9957_CR2","doi-asserted-by":"crossref","unstructured":"Ambalath, A.M., Balasundaram, R., Rao, C.H., Koppula, V., Misra, N., Philip, G., Ramanujan, M.S.: On the kernelization complexity of colorful motifs. In: Proceedings of the 5th International Symposium Parameterized and Exact Computation, pp. 14\u201325, (2010)","DOI":"10.1007\/978-3-642-17493-3_4"},{"key":"9957_CR3","doi-asserted-by":"crossref","unstructured":"Amir, A., Chan, T.M., Lewenstein, M., Lewenstein, N.: On hardness of jumbled indexing. In: Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), pp. 114\u2013125, (2014)","DOI":"10.1007\/978-3-662-43948-7_10"},{"issue":"17","key":"9957_CR4","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1016\/j.ipl.2013.05.007","volume":"113","author":"G Badkobeh","year":"2013","unstructured":"Badkobeh, G., Fici, G., Kroon, S., Lipt\u00e1k, Z.: Binary jumbled string matching for highly run-length compressible texts. Inf. Process. Lett. 113(17), 604\u2013608 (2013)","journal-title":"Inf. Process. Lett."},{"key":"9957_CR5","doi-asserted-by":"crossref","unstructured":"Benson, G.: Composition alignment. In: Proceedings of the 3rd International Workshop on Algorithms in Bioinformatics (WABI), pp. 447\u2013461, (2003)","DOI":"10.1007\/978-3-540-39763-2_32"},{"issue":"5","key":"9957_CR6","doi-asserted-by":"crossref","first-page":"1296","DOI":"10.1109\/TCBB.2011.19","volume":"8","author":"N Betzler","year":"2011","unstructured":"Betzler, N., van Bevern, R., Fellows, M.R., Komusiewicz, C., Niedermeier, R.: Parameterized algorithmics for finding connected motifs in biological networks. IEEE\/ACM Trans. Comput. Biol. Bioinform. 8(5), 1296\u20131308 (2011)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"2","key":"9957_CR7","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1093\/bioinformatics\/btl291","volume":"23","author":"S B\u00f6cker","year":"2007","unstructured":"B\u00f6cker, S.: Simulating multiplexed SNP discovery rates using base-specific cleavage and mass spectrometry. Bioinformatics 23(2), 5\u201312 (2007)","journal-title":"Bioinformatics"},{"key":"9957_CR8","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"9957_CR9","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Treewidth. Algorithmic techniques and results. In: Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 19\u201336, (1997)","DOI":"10.1007\/BFb0029946"},{"key":"9957_CR10","doi-asserted-by":"crossref","unstructured":"Burcsi, P., Cicalese F., Fici G., Lipt\u00e1k, Z.: On table arrangement, scrabble freaks, and jumbled pattern matching. In: Proceedings of the Symposium on Fun with Algorithms, pp. 89\u2013101, (2010)","DOI":"10.1007\/978-3-642-13122-6_11"},{"issue":"2","key":"9957_CR11","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1142\/S0129054112400175","volume":"23","author":"P Burcsi","year":"2012","unstructured":"Burcsi, P., Cicalese, F., Fici, G., Lipt\u00e1k, Z.: Algorithms for jumbled pattern matching in strings. Int. J. Found. Comput. Sci. 23(2), 357\u2013374 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"9957_CR12","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s00224-011-9344-5","volume":"50","author":"P Burcsi","year":"2012","unstructured":"Burcsi, P., Cicalese, F., Fici, G., Lipt\u00e1k, Z.: On approximate jumbled pattern matching in strings. Theory Comput. Syst. 50(1), 35\u201351 (2012)","journal-title":"Theory Comput. Syst."},{"issue":"7","key":"9957_CR13","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9957_CR14","unstructured":"Cicalese, F., Fici, G., Lipt\u00e1k, Z.: Searching for jumbled patterns in strings. In: Proceedings of the Prague Stringology Conference, pp. 105\u2013117, (2009)"},{"key":"9957_CR15","doi-asserted-by":"crossref","unstructured":"Cicalese, F., Gagie, T., Giaquinta, E., Laber, E., Liptak, S., Rizzi, R., Tomescu, A.I.: Indexes for jumbled pattern matching in strings, trees and graphs. In: Proceedings of the 20th International Symposium on String Processing and Information Retrieval (SPIRE), pp. 56\u201363, (2013)","DOI":"10.1007\/978-3-319-02432-5_10"},{"key":"9957_CR16","doi-asserted-by":"crossref","unstructured":"Cicalese, F., Laber, E.S., Weimann, O., Yuster, R.: Near linear time construction of an approximate index for all maximum consecutive sub-sums of a sequence. In: Proceedings of the Symposium on Combinatorial Pattern Matching, pp. 149\u2013158, (2012)","DOI":"10.1007\/978-3-642-31265-6_12"},{"issue":"1","key":"9957_CR17","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.jda.2010.09.002","volume":"9","author":"R Dondi","year":"2011","unstructured":"Dondi, R., Fertin, G., Vialette, S.: Complexity issues in vertex-colored graph pattern matching. J. Discrete Algorithms 9(1), 82\u201399 (2011)","journal-title":"J. Discrete Algorithms"},{"key":"9957_CR18","doi-asserted-by":"crossref","unstructured":"Dondi, R., Fertin, G., Vialette, S.: Finding approximate and constrained motifs in graphs. In: Proceedings of the 22nd Annual Symposium Combinatorial Pattern Matching, pp. 388\u2013401, (2011)","DOI":"10.1007\/978-3-642-21458-5_33"},{"key":"9957_CR19","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1145\/322217.322228","volume":"27","author":"PJ Downey","year":"1980","unstructured":"Downey, P.J., Sethi, R., Tarjan, R.E.: Variations on the common subexpression problem. J. ACM 27, 758\u2013771 (1980)","journal-title":"J. ACM"},{"key":"9957_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"issue":"4","key":"9957_CR21","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1016\/j.jcss.2010.07.003","volume":"77","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Upper and lower bounds for finding connected motifs in vertex-colored graphs. J. Comput. Syst. Sci. 77(4), 799\u2013811 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9957_CR22","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P.: Faster algorithm for computing the edit distance between SLP-compressed strings. In: Proceedings of the Symposium on String Processing and Information Retrieval, pp. 229\u2013236, (2012)","DOI":"10.1007\/978-3-642-34109-0_24"},{"issue":"14\u201316","key":"9957_CR23","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1016\/j.ipl.2013.04.013","volume":"113","author":"E Giaquinta","year":"2013","unstructured":"Giaquinta, E., Grabowski, S.: New algorithms for binary jumbled pattern matching. Inf. Process. Lett. 113(14\u201316), 538\u2013542 (2013)","journal-title":"Inf. Process. Lett."},{"key":"9957_CR24","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 549\u2013554, (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"9957_CR25","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W.: Efficient indexes for jumbled pattern matching with constant-sized alphabet. In: ESA, pp. 625\u2013636, (2013)","DOI":"10.1007\/978-3-642-40450-4_53"},{"issue":"4","key":"9957_CR26","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1109\/TCBB.2006.55","volume":"3","author":"V Lacroix","year":"2006","unstructured":"Lacroix, V., Fernandes, C.G., Sagot, M.-F.: Motif search in graphs: application to metabolic networks. IEEE\/ACM Trans. Comput. Biol. Bioinform. 3(4), 360\u2013368 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"18\u201319","key":"9957_CR27","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1016\/j.ipl.2010.06.012","volume":"110","author":"TM Moosa","year":"2010","unstructured":"Moosa, T.M., Rahman, M.S.: Indexing permutations for binary strings. Inf. Process. Lett. 110(18\u201319), 795\u2013798 (2010)","journal-title":"Inf. Process. Lett."},{"key":"9957_CR28","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.jda.2011.08.003","volume":"10","author":"TM Moosa","year":"2012","unstructured":"Moosa, T.M., Rahman, M.S.: Sub-quadratic time and linear space data structures for permutation matching in binary strings. J. Discrete Algorithms 10, 5\u20139 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"9957_CR29","doi-asserted-by":"crossref","unstructured":"Munro, I.: Tables. In: Proceedings of the 16th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 37\u201342, (1996)","DOI":"10.1007\/3-540-62034-6_35"},{"issue":"1\u20133","key":"9957_CR30","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel\u2013Ziv factorization to the approximation of grammar-based compression. Theoret. Comput. Sci. 302(1\u20133), 211\u2013222 (2003)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9957-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9957-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9957-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:20Z","timestamp":1559072840000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9957-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,27]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["9957"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9957-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,27]]}}}