{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:12Z","timestamp":1740109332543,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["731143"],"award-info":[{"award-number":["731143"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["LO 748\/10-2 (QUANT-KOMP)"],"award-info":[{"award-number":["LO 748\/10-2 (QUANT-KOMP)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004063","name":"Knut och Alice Wallenbergs Stiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004063","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A fringe subtree of a rooted tree is a subtree induced by one of the vertices and all its descendants. We consider the problem of estimating the number of distinct fringe subtrees in random trees under a generalized notion of distinctness, which allows for many different interpretations of what \u201cdistinct\u201d trees are. The random tree models considered are simply generated trees and families of increasing trees (recursive trees, <jats:italic>d<\/jats:italic>-ary increasing trees and generalized plane-oriented recursive trees). We prove that the order of magnitude of the number of distinct fringe subtrees (under rather mild assumptions on what \u2018distinct\u2019 means) in random trees with <jats:italic>n<\/jats:italic> vertices is <jats:inline-formula><jats:alternatives><jats:tex-math>$$n\/\\sqrt{\\log n}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mrow>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msqrt>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for simply generated trees and <jats:inline-formula><jats:alternatives><jats:tex-math>$$n\/\\log n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for increasing trees.<\/jats:p>","DOI":"10.1007\/s00453-022-01013-y","type":"journal-article","created":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T06:02:47Z","timestamp":1659333767000},"page":"3686-3728","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Distinct Fringe Subtrees in Random Trees"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3204-3801","authenticated-orcid":false,"given":"Louisa","family":"Seelbach Benkner","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5533-2764","authenticated-orcid":false,"given":"Stephan","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,1]]},"reference":[{"issue":"4","key":"1013_CR1","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1007\/s00224-015-9617-5","volume":"57","author":"S Abiteboul","year":"2015","unstructured":"Abiteboul, S., Bourhis, P., Vianu, V.: Highly expressive query languages for unordered data trees. Theory of Comput. Syst. 57(4), 927\u2013966 (2015). https:\/\/doi.org\/10.1007\/s00224-015-9617-5","journal-title":"Theory of Comput. Syst."},{"key":"1013_CR2","volume-title":"Compilers: Principles, Techniques, and Tools","author":"AV Aho","year":"1986","unstructured":"Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison-Wesley series in computer science \/ World student series edition. Addison-Wesley, Reading, MA, USA (1986)"},{"issue":"2","key":"1013_CR3","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1214\/aoap\/1177005936","volume":"1","author":"D Aldous","year":"1991","unstructured":"Aldous, D.: Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1(2), 228\u2013266 (1991). https:\/\/doi.org\/10.1214\/aoap\/1177005936","journal-title":"Ann. Appl. Probab."},{"key":"1013_CR4","volume-title":"Algebra","author":"M Artin","year":"2011","unstructured":"Artin, M.: Algebra. Pearson Prentice Hall, Upper Saddle River, NJ, USA (2011)"},{"key":"1013_CR5","doi-asserted-by":"publisher","unstructured":"Bergeron, F., Flajolet, P., Salvy, B.: Varieties of increasing trees. In: CAAP \u201992 (Rennes, 1992), Lecture Notes in Comput. Sci., vol. 581, pp. 24\u201348. Springer, Berlin (1992). https:\/\/doi.org\/10.1007\/3-540-55251-0_2","DOI":"10.1007\/3-540-55251-0_2"},{"issue":"1","key":"1013_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1002\/rsa.21056","volume":"61","author":"O Bodini","year":"2022","unstructured":"Bodini, O., Genitrini, A., Gittenberger, B., Larcher, I., Naima, M.: Compaction for two models of logarithmic-depth trees: Analysis and experiments. Random Struct. Algorithms 61(1), 31\u201361 (2022). https:\/\/doi.org\/10.1002\/rsa.21056","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"1013_CR7","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1239\/jap\/1261670685","volume":"46","author":"M B\u00f3na","year":"2009","unstructured":"B\u00f3na, M., Flajolet, P.: Isomorphism and symmetries in random phylogenetic trees. J. Appl. Probab. 46(4), 1005\u20131019 (2009). https:\/\/doi.org\/10.1239\/jap\/1261670685","journal-title":"J. Appl. Probab."},{"issue":"2","key":"1013_CR8","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00224-014-9593-1","volume":"57","author":"I Boneva","year":"2015","unstructured":"Boneva, I., Ciucanu, R., Staworko, S.: Schemas for unordered XML on a DIME. Theory of Compuing Systems 57(2), 337\u2013376 (2015). https:\/\/doi.org\/10.1007\/s00224-014-9593-1","journal-title":"Theory of Compuing Systems"},{"issue":"4","key":"1013_CR9","doi-asserted-by":"publisher","first-page":"1322","DOI":"10.1007\/s00224-014-9544-x","volume":"57","author":"M Bousquet-M\u00e9lou","year":"2015","unstructured":"Bousquet-M\u00e9lou, M., Lohrey, M., Maneth, S., Noeth, E.: XML compression via DAGs. Theory of Comput. Syst. 57(4), 1322\u20131371 (2015)","journal-title":"Theory of Comput. Syst."},{"issue":"3","key":"1013_CR10","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/136035.136043","volume":"24","author":"RE Bryant","year":"1992","unstructured":"Bryant, R.E.: Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surv. 24(3), 293\u2013318 (1992)","journal-title":"ACM Comput. Surv."},{"key":"1013_CR11","doi-asserted-by":"crossref","unstructured":"Buneman, P., Grohe, M., Koch, C.: Path queries on compressed XML. In: J.C. Freytag, et\u00a0al. (eds.) Proceedings of the 29th Conference on Very Large Data Bases, VLDB 2003, pp. 141\u2013152. Morgan Kaufmann (2003)","DOI":"10.1016\/B978-012722442-8\/50021-5"},{"key":"1013_CR12","doi-asserted-by":"crossref","unstructured":"Cai, X.S.: A study of large fringe and non-fringe subtrees in conditional galton-watson trees. Ph.D. thesis, McGill University (2016)","DOI":"10.30757\/ALEA.v14-29"},{"issue":"4","key":"1013_CR13","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1017\/S0963548309990630","volume":"19","author":"F Dennert","year":"2010","unstructured":"Dennert, F., Gr\u00fcbel, R.: On the subtree size profile of binary search trees. Comb. Probab. Comput. 19(4), 561\u2013578 (2010). https:\/\/doi.org\/10.1017\/S0963548309990630","journal-title":"Comb. Probab. Comput."},{"issue":"4","key":"1013_CR14","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0020-0190(97)00206-8","volume":"65","author":"L Devroye","year":"1998","unstructured":"Devroye, L.: On the richness of the collection of subtrees in random binary search trees. Inf. Process. Lett. 65(4), 195\u2013199 (1998)","journal-title":"Inf. Process. Lett."},{"key":"1013_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/ECP.v19-3048","volume":"19","author":"L Devroye","year":"2014","unstructured":"Devroye, L., Janson, S.: Protected nodes and fringe subtrees in some random trees. Electron. Commun. Probab. 19, 1\u201310 (2014). https:\/\/doi.org\/10.1214\/ECP.v19-3048","journal-title":"Electron. Commun. Probab."},{"key":"1013_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-211-75357-6","volume-title":"Random Trees: An Interplay Between Combinatorics and Probability","author":"M Drmota","year":"2009","unstructured":"Drmota, M.: Random Trees: An Interplay Between Combinatorics and Probability, 1st edn. Springer, Vienna, Austria (2009)","edition":"1"},{"issue":"1","key":"1013_CR17","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1239\/jap\/1269610825","volume":"47","author":"Q Feng","year":"2010","unstructured":"Feng, Q., Mahmoud, H.M.: On the variety of shapes on the fringe of a random recursive tree. J. Appl. Probab. 47(1), 191\u2013200 (2010). https:\/\/doi.org\/10.1239\/jap\/1269610825","journal-title":"J. Appl. Probab."},{"issue":"1\u20133","key":"1013_CR18","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2004.05.010","volume":"326","author":"JA Fill","year":"2004","unstructured":"Fill, J.A., Kapur, N.: Limiting distributions for additive functionals on Catalan trees. Theoret. Comput. Sci. 326(1\u20133), 69\u2013102 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.05.010","journal-title":"Theoret. Comput. Sci."},{"key":"1013_CR19","unstructured":"Finch, S.R.: Mathematical Constants. Encyclopedia of Mathematics and its Applications 94. Cambridge University Press (2003). https:\/\/www.cambridge.org\/academic\/subjects\/mathematics\/recreationalmathematics\/mathematical-constants"},{"issue":"3","key":"1013_CR20","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/(SICI)1098-2418(199710)11:3<223::AID-RSA2>3.0.CO;2-2","volume":"11","author":"P Flajolet","year":"1997","unstructured":"Flajolet, P., Gourdon, X., Mart\u00ednez, C.: Patterns in random binary search trees. Random Structures & Algorithms 11(3), 223\u2013244 (1997)","journal-title":"Random Structures & Algorithms"},{"key":"1013_CR21","doi-asserted-by":"publisher","unstructured":"Flajolet, P., Sedgewick, R.: Mellin transforms and asymptotics: finite differences and Rice\u2019s integrals. Theoret. Comput. Sci. 144(1\u20132), 101\u2013124 (1995). https:\/\/doi.org\/10.1016\/0304-3975(94)00281-M. Special volume on mathematical analysis of algorithms","DOI":"10.1016\/0304-3975(94)00281-M"},{"key":"1013_CR22","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press (2009). https:\/\/www.cambridge.org\/core\/books\/analytic-combinatorics\/7E37474C43E9B95C90BEDE082CF28708"},{"key":"1013_CR23","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Sipala, P., Steyaert, J.M.: Analytic variations on the common subexpression problem. In: Proceedings of the 17th International Colloquium on Automata, Languages and Programming, ICALP 1990, Lecture Notes in Computer Science, vol. 443, pp. 220\u2013234. Springer (1990)","DOI":"10.1007\/BFb0032034"},{"key":"1013_CR24","unstructured":"Frick, M., Grohe, M., Koch, C.: Query evaluation on compressed trees (extended abstract). In: Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, LICS 2003, pp. 188\u2013197. IEEE Computer Society Press (2003)"},{"issue":"3","key":"1013_CR25","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1017\/S096354831100071X","volume":"21","author":"M Fuchs","year":"2012","unstructured":"Fuchs, M.: Limit theorems for subtree size profiles of increasing trees. Comb. Probab. Comput. 21(3), 412\u2013441 (2012). https:\/\/doi.org\/10.1017\/S096354831100071X","journal-title":"Comb. Probab. Comput."},{"issue":"10","key":"1013_CR26","doi-asserted-by":"publisher","first-page":"6399","DOI":"10.1109\/TIT.2019.2919829","volume":"65","author":"M Ganardi","year":"2019","unstructured":"Ganardi, M., Hucke, D., Lohrey, M., Benkner, L.S.: Universal tree source coding using grammar-based compression. IEEE Trans. Inf. Theory 65(10), 6399\u20136413 (2019). https:\/\/doi.org\/10.1109\/TIT.2019.2919829","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1013_CR27","volume-title":"Probability: A Graduate Course","author":"A Gut","year":"2005","unstructured":"Gut, A.: Probability: A Graduate Course. Springer, New York (2005)"},{"key":"1013_CR28","doi-asserted-by":"publisher","unstructured":"Holmgren, C., Janson, S., \u0160ileikis, M.: Multivariate normal limit laws for the numbers of fringe subtrees in $$m$$-ary search trees and preferential attachment trees. Electron. J. Combin. 24(2), Paper No. 2.51, 49 pp. (2017). https:\/\/doi.org\/10.37236\/6374","DOI":"10.37236\/6374"},{"key":"1013_CR29","doi-asserted-by":"publisher","unstructured":"Janson, S.: Random cutting and records in deterministic and random trees. Random Structures & Algorithms 29(2), 139\u2013179 (2006). https:\/\/doi.org\/10.1002\/rsa.20086. https:\/\/onlinelibrary.wiley.com\/doi\/abs\/10.1002\/rsa.20086","DOI":"10.1002\/rsa.20086"},{"key":"1013_CR30","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1214\/11-PS188","volume":"9","author":"S Janson","year":"2012","unstructured":"Janson, S.: Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. Probab. Surv. 9, 103\u2013252 (2012). https:\/\/doi.org\/10.1214\/11-PS188","journal-title":"Probab. Surv."},{"issue":"1","key":"1013_CR31","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1002\/rsa.20568","volume":"48","author":"S Janson","year":"2016","unstructured":"Janson, S.: Asymptotic normality of fringe subtrees and additive functionals in conditioned galton-watson trees. Random Struct. Algorithms 48(1), 57\u2013101 (2016). https:\/\/doi.org\/10.1002\/rsa.20568","journal-title":"Random Struct. Algorithms"},{"key":"1013_CR32","first-page":"185","volume":"70","author":"C Jordan","year":"1869","unstructured":"Jordan, C.: Sur les assemblages de lignes. Journal f\u00fcr die reine und angewandte Mathematik 70, 185\u2013190 (1869)","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"1013_CR33","doi-asserted-by":"crossref","unstructured":"Kieffer, J.C., Yang, E.H., Szpankowski, W.: Structural complexity of random binary trees. In: Proceedings of the 2009 IEEE International Symposium on Information Theory, ISIT 2009, pp. 635\u2013639. IEEE (2009)","DOI":"10.1109\/ISIT.2009.5205704"},{"key":"1013_CR34","volume-title":"The Art of Computer Programming","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. 3. Addison-Wesley, Reading, MA (1998)"},{"key":"1013_CR35","unstructured":"Kolchin, V.F.: Random mappings \/ Valentin F. Kolchin. Translations series in mathematics and engineering. Optimization Software, New York (1986)"},{"key":"1013_CR36","doi-asserted-by":"publisher","unstructured":"Lohrey, M., Maneth, S., Reh, C.P.: Compression of unordered XML trees. In: 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, pp. 18:1\u201318:17 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2017.18","DOI":"10.4230\/LIPIcs.ICDT.2017.18"},{"issue":"5","key":"1013_CR37","doi-asserted-by":"publisher","first-page":"997","DOI":"10.4153\/CJM-1978-085-0","volume":"30","author":"A Meir","year":"1978","unstructured":"Meir, A., Moon, J.W.: On the altitude of nodes in random trees. Can. J. Math. 30(5), 997\u20131015 (1978). https:\/\/doi.org\/10.4153\/CJM-1978-085-0","journal-title":"Can. J. Math."},{"key":"1013_CR38","unstructured":"Olsson, C., Wagner, S.: Automorphisms of random trees. In: 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, LIPIcs. Leibniz Int. Proc. Inform., vol. 225, pp. 16:1\u201316:16. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2022)"},{"issue":"49","key":"1013_CR39","doi-asserted-by":"publisher","first-page":"583","DOI":"10.2307\/1969046","volume":"2","author":"R Otter","year":"1948","unstructured":"Otter, R.: The number of trees. Ann. of Math. 2(49), 583\u2013599 (1948). https:\/\/doi.org\/10.2307\/1969046","journal-title":"Ann. of Math."},{"issue":"2","key":"1013_CR40","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1002\/rsa.20161","volume":"31","author":"A Panholzer","year":"2007","unstructured":"Panholzer, A., Prodinger, H.: Level of nodes in increasing trees revisited. Random Structures Algorithms 31(2), 203\u2013226 (2007). https:\/\/doi.org\/10.1002\/rsa.20161","journal-title":"Random Structures Algorithms"},{"issue":"2","key":"1013_CR41","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/0022-0000(78)90043-0","volume":"16","author":"M Paterson","year":"1978","unstructured":"Paterson, M., Wegman, M.N.: Linear unification. J. Comput. Syst. Sci. 16(2), 158\u2013167 (1978)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1013_CR42","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1017\/s0963548318000585","volume":"28","author":"D Ralaivaosaona","year":"2019","unstructured":"Ralaivaosaona, D., Wagner, S.: A central limit theorem for additive functionals of increasing trees. Combin. Probab. Comput. 28(4), 618\u2013637 (2019). https:\/\/doi.org\/10.1017\/s0963548318000585","journal-title":"Combin. Probab. Comput."},{"key":"1013_CR43","doi-asserted-by":"crossref","unstructured":"Ralaivaosaona, D., Wagner, S.G.: Repeated fringe subtrees in random rooted trees. In: Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2015, pp. 78\u201388. SIAM (2015)","DOI":"10.1137\/1.9781611973761.7"},{"issue":"1","key":"1013_CR44","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0095-8956(92)90067-8","volume":"54","author":"F Ruskey","year":"1992","unstructured":"Ruskey, F.: Generating linear extensions of posets by transpositions. J. Combin. Theory Ser. B 54(1), 77\u2013101 (1992)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1013_CR45","doi-asserted-by":"publisher","unstructured":"Seelbach Benkner, L., Lohrey, M.: Average case analysis of leaf-centric binary tree sources. In: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, pp. 16:1\u201316:15 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.16","DOI":"10.4230\/LIPIcs.MFCS.2018.16"},{"key":"1013_CR46","doi-asserted-by":"publisher","unstructured":"Seelbach Benkner, L., Wagner, S.G.: On the collection of fringe subtrees in random binary trees. In: Y.\u00a0Kohayakawa, F.K. Miyazawa (eds.) LATIN 2020: Theoretical Informatics - 14th Latin American Symposium, S\u00e3o Paulo, Brazil, January 5-8, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12118, pp. 546\u2013558. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-61792-9_43","DOI":"10.1007\/978-3-030-61792-9_43"},{"issue":"3","key":"1013_CR47","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1109\/TIT.2013.2295392","volume":"60","author":"J Zhang","year":"2014","unstructured":"Zhang, J., Yang, E.H., Kieffer, J.C.: A universal grammar-based code for lossless compression of binary trees. IEEE Trans. Inf. Theory 60(3), 1373\u20131386 (2014)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"6","key":"1013_CR48","doi-asserted-by":"publisher","first-page":"1113","DOI":"10.1109\/TCYB.2014.2345579","volume":"45","author":"S Zhang","year":"2015","unstructured":"Zhang, S., Du, Z., Wang, J.T.: New techniques for mining frequent patterns in unordered trees. IEEE Transactions on Cybernetics 45(6), 1113\u20131125 (2015). https:\/\/doi.org\/10.1109\/TCYB.2014.2345579","journal-title":"IEEE Transactions on Cybernetics"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01013-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01013-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01013-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T12:12:20Z","timestamp":1669637540000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01013-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,1]]},"references-count":48,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["1013"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01013-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,8,1]]},"assertion":[{"value":"6 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflicts\/competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest\/Competing interests:"}}]}}