{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T18:26:45Z","timestamp":1778783205773,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,9,5]],"date-time":"2012-09-05T00:00:00Z","timestamp":1346803200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,3]]},"DOI":"10.1007\/s00453-012-9683-x","type":"journal-article","created":{"date-parts":[[2012,9,4]],"date-time":"2012-09-04T16:39:41Z","timestamp":1346776781000},"page":"610-625","source":"Crossref","is-referenced-by-count":26,"title":["On Cartesian Trees and Range Minimum Queries"],"prefix":"10.1007","volume":"68","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","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":[[2012,9,5]]},"reference":[{"key":"9683_CR1","first-page":"237","volume-title":"Proceedings of the 19th Annual ACM Symposium on Computational Geometry (SCG)","author":"P.K. Agarwal","year":"2003","unstructured":"Agarwal, P.K., Arge, L., Danner, A., Holland-Minkley, B.: Cache-oblivious data structures for orthogonal range searching. In: Proceedings of the 19th Annual ACM Symposium on Computational Geometry (SCG), pp. 237\u2013245 (2003)"},{"issue":"9","key":"9683_CR2","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"9683_CR3","unstructured":"Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical report, TR-71\/87, Institute of Computer Science, Tel Aviv University (1987)"},{"issue":"4","key":"9683_CR4","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., Spork, M.: Optimal on-line decremental connectivity in trees. Inf. Process. Lett. 64(4), 161\u2013164 (1997)","journal-title":"Inf. Process. Lett."},{"key":"9683_CR5","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-540-73437-6_29","volume-title":"Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM)","author":"A. Amir","year":"2007","unstructured":"Amir, A., Fischer, J., Lewenstein, M.: Two-dimensional range minimum queries. In: Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 286\u2013294 (2007)"},{"issue":"6","key":"9683_CR6","doi-asserted-by":"crossref","first-page":"1672","DOI":"10.1137\/S0097539703428324","volume":"36","author":"L. Arge","year":"2007","unstructured":"Arge, L., Bender, M.A., Demaine, E.D., Holland-Minkley, B., Munro, J.I.: An optimal cache-oblivious priority queue and its application to graph algorithms. SIAM J. Comput. 36(6), 1672\u20131695 (2007)","journal-title":"SIAM J. Comput."},{"key":"9683_CR7","first-page":"150","volume-title":"Proceedings of the 21st Annual Symposium on Discrete Algorithms (SODA)","author":"M.J. Atallah","year":"2010","unstructured":"Atallah, M.J., Yuan, H.: Data structures for range minimum queries in multidimensional arrays. In: Proceedings of the 21st Annual Symposium on Discrete Algorithms (SODA), pp. 150\u2013160 (2010)"},{"key":"9683_CR8","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Demaine, E.D., Farach-colton, M.: Cache-oblivious B-trees. SIAM J. Comput. 399\u2013409 (2000)","DOI":"10.1109\/SFCS.2000.892128"},{"issue":"2","key":"9683_CR9","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms 57(2), 75\u201394 (2005)","journal-title":"J. Algorithms"},{"issue":"2","key":"9683_CR10","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0222017","volume":"22","author":"O. Berkman","year":"1993","unstructured":"Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM J. Comput. 22(2), 221\u2013242 (1993)","journal-title":"SIAM J. Comput."},{"key":"9683_CR11","first-page":"581","volume-title":"Proceedings of the 17th Annual Symp. on Discrete Algorithms (SODA)","author":"G.S. Brodal","year":"2006","unstructured":"Brodal, G.S., Fagerberg, R.: Cache-oblivious string dictionaries. In: Proceedings of the 17th Annual Symp. on Discrete Algorithms (SODA), pp.\u00a0581\u2013590 (2006)"},{"issue":"6","key":"9683_CR12","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"B. Chazelle","year":"2000","unstructured":"Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47(6), 1028\u20131047 (2000)","journal-title":"J. ACM"},{"key":"9683_CR13","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1145\/73833.73848","volume-title":"Proceedings of the 5th Annual ACM Symposium on Computational Geometry (SCG)","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B., Rosenberg, B.: Computing partial sums in multidimensional arrays. In: Proceedings of the 5th Annual ACM Symposium on Computational Geometry (SCG), pp. 131\u2013139 (1989)"},{"key":"9683_CR14","first-page":"235","volume-title":"Proceedings of the 10th Annual Symposium on Discrete Algorithms (SODA)","author":"R. Cole","year":"1999","unstructured":"Cole, R., Hariharan, R.: Dynamic LCA queries on trees. In: Proceedings of the 10th Annual Symposium on Discrete Algorithms (SODA), pp. 235\u2013244 (1999)"},{"key":"9683_CR15","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/978-3-642-02927-1_29","volume-title":"Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP)","author":"E.D. Demaine","year":"2009","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian trees and range minimum queries. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), pp. 341\u2013353 (2009)"},{"key":"9683_CR16","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1137\/1.9781611973068.43","volume-title":"Proceedings of the 20th Annual Symposium on Discrete Algorithms (SODA)","author":"R. Duan","year":"2009","unstructured":"Duan, R., Pettie, S.: Fast algorithms for (max,min)-matrix multiplication and bottleneck shortest paths. In: Proceedings of the 20th Annual Symposium on Discrete Algorithms (SODA), pp. 384\u2013391 (2009)"},{"key":"9683_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/322234.322235","volume":"28","author":"S. Even","year":"1981","unstructured":"Even, S., Shiloach, Y.: An on-line edge deletion problem. J. ACM 28, 1\u20134 (1981)","journal-title":"J. ACM"},{"key":"9683_CR18","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/11780441_5","volume-title":"Proceedings of the 17th Symposium on Combinatorial Pattern Matching (CPM)","author":"J. Fischer","year":"2006","unstructured":"Fischer, J., Heun, V.: Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE. In: Proceedings of the 17th Symposium on Combinatorial Pattern Matching (CPM), pp. 36\u201348 (2006)"},{"key":"9683_CR19","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M.L. Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47, 424\u2013433 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"9683_CR20","first-page":"285","volume-title":"Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS)","author":"M. Frigo","year":"1999","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS), pp. 285\u2013298 (1999)"},{"key":"9683_CR21","first-page":"135","volume-title":"Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC)","author":"H. Gabow","year":"1984","unstructured":"Gabow, H., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pp. 135\u2013143 (1984)"},{"issue":"2","key":"9683_CR22","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9683_CR23","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1287\/opre.9.6.898","volume":"9","author":"T.C. Hu","year":"1961","unstructured":"Hu, T.C.: The maximum capacity route problem. Oper. Res. 9(6), 898\u2013900 (1961)","journal-title":"Oper. Res."},{"key":"9683_CR24","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"D.R. Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm for finding minimum spanning trees. J. ACM 42, 321\u2013329 (1995)","journal-title":"J. ACM"},{"key":"9683_CR25","doi-asserted-by":"crossref","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SICOMP: SIAM J. Comput. 34 (2005)","DOI":"10.1137\/S0097539703433912"},{"key":"9683_CR26","volume-title":"The Art of Computer Programming Volume 4 Fascicle 4: Generating All Trees; History of Combinatorial Generation","author":"D.E. Knuth","year":"2006","unstructured":"Knuth, D.E.: The Art of Computer Programming Volume 4 Fascicle 4: Generating All Trees; History of Combinatorial Generation. Addison-Wesley, Reading (2006)"},{"issue":"1","key":"9683_CR27","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF02579443","volume":"5","author":"J. Koml\u00f3s","year":"1985","unstructured":"Koml\u00f3s, J.: Linear verification for spanning trees. Combinatorica 5(1), 57\u201365 (1985)","journal-title":"Combinatorica"},{"key":"9683_CR28","first-page":"565","volume-title":"Proceedings of the 18th Annual Symposium on Discrete Algorithms (SODA)","author":"T. Kopelowitz","year":"2007","unstructured":"Kopelowitz, T., Lewenstein, M.: Dynamic weighted ancestors. In: Proceedings of the 18th Annual Symposium on Discrete Algorithms (SODA), pp. 565\u2013574 (2007)"},{"key":"9683_CR29","first-page":"155","volume-title":"Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS)","author":"S. Pettie","year":"2002","unstructured":"Pettie, S.: An inverse-Ackermann style lower bound for the online minimum spanning tree. In: Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS), pp. 155\u2013163 (2002)"},{"key":"9683_CR30","first-page":"713","volume-title":"Proceedings of the 13th Annual Symposium on Discrete Algorithms (SODA)","author":"S. Pettie","year":"2002","unstructured":"Pettie, S., Ramachandran, V.: Minimizing randomness in minimum spanning tree, parallel connectivity and set maxima algorithms. In: Proceedings of the 13th Annual Symposium on Discrete Algorithms (SODA), pp. 713\u2013722 (2002)"},{"issue":"1","key":"9683_CR31","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/505241.505243","volume":"49","author":"S. Pettie","year":"2002","unstructured":"Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. ACM 49(1), 16\u201334 (2002)","journal-title":"J. ACM"},{"issue":"5","key":"9683_CR32","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1287\/opre.8.5.733","volume":"8","author":"M. Pollack","year":"1960","unstructured":"Pollack, M.: The maximum capacity through a network. Oper. Res. 8(5), 733\u2013736 (1960)","journal-title":"Oper. Res."},{"key":"9683_CR33","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"Schieber, B., Vishkin, U.: On finding lowest common ancestors: simplification and parallelization. SIAM J. Comput. 17, 1253\u20131262 (1988)","journal-title":"SIAM J. Comput."},{"key":"9683_CR34","unstructured":"Seidel, R.: Understanding the inverse Ackermann function. PDF presenttion. Available at http:\/\/cgi.di.uoa.gr\/~ewcg06\/invited\/Seidel.pdf"},{"key":"9683_CR35","first-page":"978","volume-title":"Proceedings of the 18th Annual Symposium on Discrete Algorithms (SODA)","author":"A. Shapira","year":"2007","unstructured":"Shapira, A., Yuster, R., Zwick, U.: All-pairs bottleneck paths in vertex weighted graphs. In: Proceedings of the 18th Annual Symposium on Discrete Algorithms (SODA), pp. 978\u2013985 (2007)"},{"issue":"3","key":"9683_CR36","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"9683_CR37","first-page":"235","volume-title":"Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC)","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary trees. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC), pp. 235\u2013245 (1983)"},{"key":"9683_CR38","first-page":"585","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC)","author":"V. Vassilevska","year":"2007","unstructured":"Vassilevska, V., Williams, R., Yuster, R.: All-pairs bottleneck paths for general graphs in truly sub-cubic time. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 585\u2013589 (2007)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9683-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9683-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9683-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T21:18:53Z","timestamp":1744060733000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9683-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,5]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["9683"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9683-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,5]]}}}