{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:12:38Z","timestamp":1750219958798,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,6,24]],"date-time":"2023-06-24T00:00:00Z","timestamp":1687564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Union\u2019s Horizon 2020","award":["734922"],"award-info":[{"award-number":["734922"]}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Fonds de la Recherche Scientifique-FNRS","award":["J.0146.18, and MISU F 6001 1"],"award-info":[{"award-number":["J.0146.18, and MISU F 6001 1"]}]},{"name":"NSF AitF","award":["1533564"],"award-info":[{"award-number":["1533564"]}]},{"name":"Fonds de la Recherche Scientifique-FNRS","award":["40000886"],"award-info":[{"award-number":["40000886"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"<jats:p>\n            We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online\n            <jats:italic>O<\/jats:italic>\n            (log log\n            <jats:italic>n<\/jats:italic>\n            )-competitive search tree data structure in this model, where\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices. This matches the best-known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one that we call Steiner-closed search trees, which may be of independent interest. Moreover, our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees and, second, from these trees into paths.\n          <\/jats:p>","DOI":"10.1145\/3595180","type":"journal-article","created":{"date-parts":[[2023,4,28]],"date-time":"2023-04-28T11:55:57Z","timestamp":1682682957000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Competitive Online Search Trees on Trees"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8906-0573","authenticated-orcid":false,"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[{"name":"Carleton University, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2312-0967","authenticated-orcid":false,"given":"Jean","family":"Cardinal","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles (ULB), Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8885-8172","authenticated-orcid":false,"given":"John","family":"Iacono","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles (ULB), Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4928-103X","authenticated-orcid":false,"given":"Grigorios","family":"Koumoutsos","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles (ULB), Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6999-3088","authenticated-orcid":false,"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles (ULB), Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,24]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"1259","article-title":"An algorithm for the organization of information","volume":"3","author":"Adel\u2019son-Vel\u2019skii G. M.","year":"1962","unstructured":"G. M. Adel\u2019son-Vel\u2019skii and E. M. Landis. 1962. An algorithm for the organization of information. Soviet Mathematics - Doklady 3, (1962), 1259\u20131263.","journal-title":"Soviet Mathematics - Doklady"},{"issue":"4","key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1007\/BF01934264","article-title":"Finding minimum height elimination trees for interval graphs in polynomial time","volume":"34","author":"Aspvall Bengt","year":"1994","unstructured":"Bengt Aspvall and Pinar Heggernes. 1994. Finding minimum height elimination trees for interval graphs in polynomial time. BIT Numer. Math. 34, 4 (01 December1994), 484\u2013509.","journal-title":"BIT Numer. Math."},{"issue":"6","key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"2090","DOI":"10.1137\/S009753979731858X","article-title":"Optimal search in trees","volume":"28","author":"Ben-Asher Yosi","year":"1999","unstructured":"Yosi Ben-Asher, Eitan Farchi, and Ilan Newman. 1999. Optimal search in trees. SIAM J. Comput. 28, 6 (1999), 2090\u20132102.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1137\/S0895480195282550","article-title":"Rankings of graphs","volume":"11","author":"Bodlaender Hans L.","year":"1998","unstructured":"Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko M\u00fcller, and Zsolt Tuza. 1998. Rankings of graphs. SIAM J. Discr. Math. 11, 1 (1998), 168\u2013181.","journal-title":"SIAM J. Discr. Math."},{"issue":"2","key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1006\/jagm.1995.1009","article-title":"Approximating treewidth, pathwidth, frontsize, and shortest elimination tree","volume":"18","author":"Bodlaender Hans L.","year":"1995","unstructured":"Hans L. Bodlaender, John R. Gilbert, Hj\u00e1lmtyr Hafsteinsson, and Ton Kloks. 1995. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algor. 18, 2 (1995), 238\u2013255.","journal-title":"J. Algor."},{"issue":"4","key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"1264","DOI":"10.1007\/s00453-016-0224-x","article-title":"The power and limitations of static binary search trees with lazy finger","volume":"76","author":"Bose Prosenjit","year":"2016","unstructured":"Prosenjit Bose, Karim Dou\u00efeb, John Iacono, and Stefan Langerman. 2016. The power and limitations of static binary search trees with lazy finger. Algorithmica 76, 4 (2016), 1264\u20131275.","journal-title":"Algorithmica"},{"issue":"4","key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"P4.18","DOI":"10.37236\/7762","article-title":"On the diameter of tree associahedra","volume":"25","author":"Cardinal Jean","year":"2018","unstructured":"Jean Cardinal, Stefan Langerman, and Pablo P\u00e9rez-Lantero. 2018. On the diameter of tree associahedra. Electr. J. Comb. 25, 4 (2018), P4.18.","journal-title":"Electr. J. Comb."},{"issue":"12","key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"2155","DOI":"10.1016\/j.topol.2005.08.010","article-title":"Coxeter complexes and graph-associahedra","volume":"153","author":"Carr Michael","year":"2006","unstructured":"Michael Carr and Satyan L. Devadoss. 2006. Coxeter complexes and graph-associahedra. Topol. Appl. 153, 12 (2006), 2155\u20132168.","journal-title":"Topol. Appl."},{"issue":"5","key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/s00493-014-2959-9","article-title":"Many non-equivalent realizations of the associahedron","volume":"35","author":"Ceballos Cesar","year":"2015","unstructured":"Cesar Ceballos, Francisco Santos, and G\u00fcnter M. Ziegler. 2015. Many non-equivalent realizations of the associahedron. Combinatorica 35, 5 (01 October2015), 513\u2013551.","journal-title":"Combinatorica"},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1109\/FOCS.2015.32","volume-title":"Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS\u201915)","author":"Chalermsook Parinya","year":"2015","unstructured":"Parinya Chalermsook, Mayank Goswami, L\u00e1szl\u00f3 Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. 2015. Pattern-avoiding access in binary search trees. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS\u201915). 410\u2013423."},{"key":"e_1_3_2_12_2","first-page":"300","volume-title":"Proceedings of the 23rd Annual European Symposium on Algorithms (ESA\u201915)","author":"Chalermsook Parinya","year":"2015","unstructured":"Parinya Chalermsook, Mayank Goswami, L\u00e1szl\u00f3 Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. 2015. Self-adjusting binary search trees: What makes them tick?. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA\u201915). 300\u2013312."},{"issue":"50","key":"e_1_3_2_13_2","doi-asserted-by":"crossref","first-page":"6879","DOI":"10.1016\/j.tcs.2011.08.042","article-title":"On the complexity of searching in trees and partially ordered structures","volume":"412","author":"Cicalese Ferdinando","year":"2011","unstructured":"Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Marco Molinaro. 2011. On the complexity of searching in trees and partially ordered structures. Theor. Comput. Sci. 412, 50 (2011), 6879\u20136896.","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"e_1_3_2_14_2","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1007\/s00453-012-9715-6","article-title":"Improved approximation algorithms for the average-case tree searching problem","volume":"68","author":"Cicalese Ferdinando","year":"2014","unstructured":"Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Marco Molinaro. 2014. Improved approximation algorithms for the average-case tree searching problem. Algorithmica 68, 4 (2014), 1045\u20131074.","journal-title":"Algorithmica"},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.tcs.2016.07.019","article-title":"On the tree search problem with non-uniform costs","volume":"647","author":"Cicalese Ferdinando","year":"2016","unstructured":"Ferdinando Cicalese, Bal\u00e1zs Keszegh, Bernard Lidick\u00fd, D\u00f6m\u00f6t\u00f6r P\u00e1lv\u00f6lgyi, and Tom\u00e1s Valla. 2016. On the tree search problem with non-uniform costs. Theor. Comput. Sci. 647 (2016), 22\u201332.","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1137\/S009753979732699X","article-title":"On the dynamic finger conjecture for splay trees. Part II: The proof","volume":"30","author":"Cole Richard","year":"2000","unstructured":"Richard Cole. 2000. On the dynamic finger conjecture for splay trees. Part II: The proof. SIAM J. Comput. 30, 1 (2000), 44\u201385.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539797326988","article-title":"On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences","volume":"30","author":"Cole Richard","year":"2000","unstructured":"Richard Cole, Bud Mishra, Jeanette P. Schmidt, and Alan Siegel. 2000. On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences. SIAM J. Comput. 30, 1 (2000), 1\u201343.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_18_2","volume-title":"Introduction to Algorithms, 3rd Edition","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press."},{"key":"e_1_3_2_19_2","first-page":"496","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909)","author":"Demaine Erik D.","year":"2009","unstructured":"Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, and Mihai P\u01cetra\u015fcu. 2009. The geometry of binary search trees. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909). 496\u2013505."},{"issue":"1","key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1137\/S0097539705447347","article-title":"Dynamic optimality\u2014Almost","volume":"37","author":"Demaine Erik D.","year":"2007","unstructured":"Erik D. Demaine, Dion Harmon, John Iacono, and Mihai P\u01cetra\u015fcu. 2007. Dynamic optimality\u2014Almost. SIAM J. Comput. 37, 1 (2007), 240\u2013251.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0166-218X(99)00179-1","article-title":"On the vertex ranking problem for trapezoid, circular-arc and other graphs","volume":"98","author":"Deogun Jitender S.","year":"1999","unstructured":"Jitender S. Deogun, Ton Kloks, Dieter Kratsch, and Haiko M\u00fcller. 1999. On the vertex ranking problem for trapezoid, circular-arc and other graphs. Discr. Appl. Math. 98, 1 (1999), 39\u201363.","journal-title":"Discr. Appl. Math."},{"key":"e_1_3_2_22_2","first-page":"519","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201916)","author":"Emamjomeh-Zadeh Ehsan","year":"2016","unstructured":"Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal. 2016. Deterministic and probabilistic binary search in graphs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201916). 519\u2013532."},{"key":"e_1_3_2_23_2","first-page":"240","volume-title":"Proceedings of the 7th Annual ACM Symposium on Theory of Computing","author":"Fredman Michael L.","year":"1975","unstructured":"Michael L. Fredman. 1975. Two applications of a probabilistic search technique: Sorting x + y and building balanced search trees. In Proceedings of the 7th Annual ACM Symposium on Theory of Computing. 240\u2013244."},{"issue":"1","key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.ipl.2007.10.001","article-title":"Chain-splay trees, or, how to achieve and prove loglogN-competitiveness by splaying","volume":"106","author":"Georgakopoulos George F.","year":"2008","unstructured":"George F. Georgakopoulos. 2008. Chain-splay trees, or, how to achieve and prove loglogN-competitiveness by splaying. Inf. Process. Lett. 106, 1 (2008), 37\u201343.","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1093\/comjnl\/47.1.10","article-title":"Generalized template splay: A basic theory and calculus","volume":"47","author":"Georgakopoulos George F.","year":"2004","unstructured":"George F. Georgakopoulos and David J. McClurkin. 2004. Generalized template splay: A basic theory and calculus. Comput. J. 47, 1 (2004), 10\u201319.","journal-title":"Comput. J."},{"key":"e_1_3_2_26_2","first-page":"8","volume-title":"Proceedings of the 19th Annual Symposium on Foundations of Computer Science","author":"Guibas Leonidas J.","year":"1978","unstructured":"Leonidas J. Guibas and Robert Sedgewick. 1978. A dichromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science. 8\u201321."},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","unstructured":"Frank Harary. 1969. Graph Theory . Addison-Wesley.","DOI":"10.21236\/AD0705364"},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1007\/978-3-642-22300-6_43","volume-title":"Proceedings of the 12th International Symposium on Algorithms and Data Structures (WADS\u201911)","author":"Heeringa Brent","year":"2011","unstructured":"Brent Heeringa, Marius Catalin Iordan, and Louis Theran. 2011. Searching in dynamic tree-like partial orders. In Proceedings of the 12th International Symposium on Algorithms and Data Structures (WADS\u201911). 512\u2013523."},{"key":"e_1_3_2_29_2","first-page":"236","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms\u2014Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday","author":"Iacono John","year":"2013","unstructured":"John Iacono. 2013. In pursuit of the dynamic optimality conjecture. In Space-Efficient Data Structures, Streams, and Algorithms\u2014Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. 236\u2013250."},{"key":"e_1_3_2_30_2","first-page":"672","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Iacono John","year":"2016","unstructured":"John Iacono and Stefan Langerman. 2016. Weighted dynamic finger in binary search trees. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). 672\u2013691."},{"key":"e_1_3_2_31_2","first-page":"185","article-title":"Sur les assemblages de lignes","volume":"70","author":"Jordan Camille","year":"1869","unstructured":"Camille Jordan. 1869. Sur les assemblages de lignes. J. reine angew. Math. 70 (1869), 185\u2013190.","journal-title":"J. reine angew. Math."},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/BF00264289","article-title":"Optimum binary search trees","volume":"1","author":"Knuth Donald E.","year":"1971","unstructured":"Donald E. Knuth. 1971. Optimum binary search trees. Acta Inf. 1 (1971), 14\u201325.","journal-title":"Acta Inf."},{"issue":"6","key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1016\/S0195-6698(89)80072-1","article-title":"The associahedron and triangulations of the n-gon","volume":"10","author":"Lee Carl W.","year":"1989","unstructured":"Carl W. Lee. 1989. The associahedron and triangulations of the n-gon. Eur. J. Combin. 10, 6 (1989), 551\u2013560.","journal-title":"Eur. J. Combin."},{"key":"e_1_3_2_34_2","unstructured":"Joan M. Lucas. 1988. Canonical Forms for Competitive Binary Search Tree Algorithms. DGS-TR-250 Department of Computer Science Hill Center for the Mathematical Sciences Busch Campus Rutgers University."},{"key":"e_1_3_2_35_2","article-title":"Graph properties of graph associahedra","volume":"73","author":"Manneville Thibault","year":"2015","unstructured":"Thibault Manneville and Vincent Pilaud. 2015. Graph properties of graph associahedra. S\u00e9min. Lothar. Combin. B73d (2015).","journal-title":"S\u00e9min. Lothar. Combin."},{"key":"e_1_3_2_36_2","first-page":"287","article-title":"Nearly optimal binary search trees","volume":"5","author":"Mehlhorn Kurt","year":"1975","unstructured":"Kurt Mehlhorn. 1975. Nearly optimal binary search trees. Acta Inf. 5 (1975), 287\u2013295.","journal-title":"Acta Inf."},{"issue":"2","key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1137\/0206017","article-title":"A best possible bound for the weighted path length of binary search trees","volume":"6","author":"Mehlhorn Kurt","year":"1977","unstructured":"Kurt Mehlhorn. 1977. A best possible bound for the weighted path length of binary search trees. SIAM J. Comput. 6, 2 (1977), 235\u2013239.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_38_2","first-page":"1096","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Mozes Shay","year":"2008","unstructured":"Shay Mozes, Krzysztof Onak, and Oren Weimann. 2008. Finding an optimal tree searching strategy in linear time. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 1096\u20131105."},{"key":"e_1_3_2_39_2","series-title":"Proceeding of the 8th European Symposium on Algorithms (ESA\u201900)","first-page":"338","volume":"1879","author":"Munro J. Ian","year":"2000","unstructured":"J. Ian Munro. 2000. On the competitiveness of linear search. In Proceeding of the 8th European Symposium on Algorithms (ESA\u201900), Lecture Notes in Computer Science, Vol. 1879. Springer, 338\u2013345."},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/978-3-642-27875-4_6","volume-title":"Sparsity: Graphs, Structures, and Algorithms","author":"Ne\u0161et\u0159il Jaroslav","year":"2012","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity: Graphs, Structures, and Algorithms. Springer, Chapter 6, 115\u2013144."},{"key":"e_1_3_2_41_2","first-page":"379","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906)","author":"Onak Krzysztof","year":"2006","unstructured":"Krzysztof Onak and Pawel Parys. 2006. Generalization of binary search: Searching in trees and forest-like partial orders. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906). 379\u2013388."},{"issue":"6","key":"e_1_3_2_42_2","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1093\/imrn\/rnn153","article-title":"Permutohedra, associahedra, and beyond","volume":"2009","author":"Postnikov Alexander","year":"2009","unstructured":"Alexander Postnikov. 2009. Permutohedra, associahedra, and beyond. Int. Math. Res. Not. 2009, 6 (2009), 1026\u20131106.","journal-title":"Int. Math. Res. Not."},{"key":"e_1_3_2_43_2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.4171\/dm\/248","article-title":"Faces of generalized permutohedra.","volume":"13","author":"Postnikov Alex","year":"2008","unstructured":"Alex Postnikov, Victor Reiner, and Lauren Williams. 2008. Faces of generalized permutohedra. Doc. Math. 13 (2008), 207\u2013273.","journal-title":"Doc. Math."},{"key":"e_1_3_2_44_2","unstructured":"Alex Pothen. 1988. The Complexity of Optimal Elimination Trees . Technical Report CS-88-13 Pennsylvania State University."},{"key":"e_1_3_2_45_2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.aim.2014.02.035","article-title":"The diameter of associahedra","volume":"259","author":"Pournin Lionel","year":"2014","unstructured":"Lionel Pournin. 2014. The diameter of associahedra. Adv. Math. 259 (2014), 13\u201342.","journal-title":"Adv. Math."},{"issue":"2","key":"e_1_3_2_46_2","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0020-0190(89)90161-0","article-title":"Optimal node ranking of trees in linear time","volume":"33","author":"Sch\u00e4ffer Alejandro A.","year":"1989","unstructured":"Alejandro A. Sch\u00e4ffer. 1989. Optimal node ranking of trees in linear time. Inform. Process. Lett. 33, 2 (1989), 91\u201396.","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"e_1_3_2_47_2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon Claude Elwood","year":"1948","unstructured":"Claude Elwood Shannon. 1948. A mathematical theory of communication. Bell Syst. Techn. J. 27, 3 (71948), 379\u2013423.","journal-title":"Bell Syst. Techn. J."},{"issue":"3","key":"e_1_3_2_48_2","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","article-title":"A data structure for dynamic trees","volume":"26","author":"Sleator Daniel Dominic","year":"1983","unstructured":"Daniel Dominic Sleator and Robert Endre Tarjan. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 3 (1983), 362\u2013391.","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"e_1_3_2_49_2","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","article-title":"Self-adjusting binary search trees","volume":"32","author":"Sleator Daniel Dominic","year":"1985","unstructured":"Daniel Dominic Sleator and Robert Endre Tarjan. 1985. Self-adjusting binary search trees. J. ACM 32, 3 (1985), 652\u2013686.","journal-title":"J. ACM"},{"key":"e_1_3_2_50_2","first-page":"122","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing","author":"Sleator Daniel Dominic","year":"1986","unstructured":"Daniel Dominic Sleator, Robert Endre Tarjan, and William P. Thurston. 1986. Rotation distance, triangulations, and hyperbolic geometry. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing. 122\u2013135."},{"issue":"2","key":"e_1_3_2_51_2","first-page":"275","article-title":"Homotopy associativity of H-spaces. I","volume":"108","author":"Stasheff James Dillon","year":"1963","unstructured":"James Dillon Stasheff. 1963. Homotopy associativity of H-spaces. I. Trans. Am. Math. Soc. 108, 2 (1963), 275\u2013292.","journal-title":"Trans. Am. Math. Soc."},{"issue":"3","key":"e_1_3_2_52_2","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jagm.1996.0025","article-title":"An explanation of splaying","volume":"20","author":"Subramanian Ashok","year":"1996","unstructured":"Ashok Subramanian. 1996. An explanation of splaying. J. Algor. 20, 3 (1996), 512\u2013525.","journal-title":"J. Algor."},{"key":"e_1_3_2_53_2","volume-title":"Mono\u00efdes pr\u00e9ordonn\u00e9s et cha\u00eenes de Malcev","author":"Tamari Dov","year":"1951","unstructured":"Dov Tamari. 1951. Mono\u00efdes pr\u00e9ordonn\u00e9s et cha\u00eenes de Malcev. Th\u00e8se de Math\u00e9matiques, Paris."},{"key":"e_1_3_2_54_2","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"Tarjan Robert Endre","year":"1983","unstructured":"Robert Endre Tarjan. 1983. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA."},{"key":"e_1_3_2_55_2","first-page":"374","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201906)","author":"Wang Chengwen Chris","year":"2006","unstructured":"Chengwen Chris Wang, Jonathan Derryberry, and Daniel Dominic Sleator. 2006. O(log log n)-competitive dynamic binary search trees. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201906). 374\u2013383."},{"issue":"1","key":"e_1_3_2_56_2","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/0218004","article-title":"Lower bounds for accessing binary search trees with rotations","volume":"18","author":"Wilber Robert E.","year":"1989","unstructured":"Robert E. Wilber. 1989. Lower bounds for accessing binary search trees with rotations. SIAM J. Comput. 18, 1 (1989), 56\u201367.","journal-title":"SIAM J. Comput."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3595180","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3595180","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:08Z","timestamp":1750182548000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3595180"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,24]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3595180"],"URL":"https:\/\/doi.org\/10.1145\/3595180","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2023,6,24]]},"assertion":[{"value":"2020-12-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}