Abstract
We present new results on Cartesian trees with applications in range minimum queries and bottleneck edge queries. We introduce a cache-oblivious Cartesian tree for solving the range minimum query problem, a Cartesian tree of a tree for the bottleneck edge query problem on trees and undirected graphs, and a proof that no Cartesian tree exists for the two-dimensional version of the range minimum query problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
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–245 (2003)
Aggarwal, A., Vitter, J.S.: The input/output complexity of sorting and related problems. Communications of the ACM 31(9), 1116–1127 (1988)
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)
Alstrup, S., Spork, M.: Optimal on-line decremental connectivity in trees. Information Processing Letters 64(4), 161–164 (1997)
Amir, A., Fischer, J., Lewenstein, M.: Two-dimensional range minimum queries. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 286–294. Springer, Heidelberg (2007)
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 Journal on Computing 36(6), 1672–1695 (2007)
Atallah, M.J., Yuan, H.: Data structures for range minimum queries in multidimensional arrays (manuscript, 2009)
Bender, M.A., Demaine, E.D., Farach-colton, M.: Cache-oblivious B-trees. SIAM Journal on Computing, 399–409 (2000)
Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. Journal of Algorithms 57(2), 75–94 (2005)
Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM Journal on Computing 22(2), 221–242 (1993)
Brodal, G.S., Fagerberg, R.: Cache-oblivious string dictionaries. In: Proceedings of the 17th annual Symp. On Discrete Algorithms (SODA), pp. 581–590 (2006)
Chazelle, B.: A minimum spanning tree algorithm with inverse-ackermann type complexity. Journal of the ACM 47(6), 1028–1047 (2000)
Chazelle, B., Rosenberg, B.: Computing partial sums in multidimensional arrays. In: Proceedings of the 5th annual ACM Symposium on Computational Geometry (SCG), pp. 131–139 (1989)
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 (2009)
Even, S., Shiloach, Y.: An on-line edge deletion problem. Journal of the ACM 28, 1–4 (1981)
Fischer, J., Heun, V.: Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol. 4009, pp. 36–48. Springer, Heidelberg (2006)
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–298 (1999)
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–143 (1984)
Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing 13(2), 338–355 (1984)
Hu, T.C.: The maximum capacity route problem. Operations Research 9(6), 898–900 (1961)
Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm for finding minimum spanning trees. Journal of the ACM 42, 321–329 (1995)
Knuth, D.E.: The Art of Computer Programming Volume 4 Fascicle 4: Generating All Trees; History of Combinatorial Generation. Addison-Wesley, Reading (2006)
Komlós, J.: Linear verification for spanning trees. Combinatorica 5(1), 57–65 (1985)
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–163 (2002)
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–722 (2002)
Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. Journal of the ACM 49(1), 16–34 (2002)
Pollack, M.: The maximum capacity through a network. Operations Research 8(5), 733–736 (1960)
Schieber, B., Vishkin, U.: On finding lowest common ancestors: Simplification and parallelization. SIAM Journal on Computing 17, 1253–1262 (1988)
Seidel, R.: Understanding the inverse ackermann function. PDF presenttion, http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.pdf
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–985 (2007)
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–589 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Demaine, E.D., Landau, G.M., Weimann, O. (2009). On Cartesian Trees and Range Minimum Queries. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds) Automata, Languages and Programming. ICALP 2009. Lecture Notes in Computer Science, vol 5555. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02927-1_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-02927-1_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02926-4
Online ISBN: 978-3-642-02927-1
eBook Packages: Computer ScienceComputer Science (R0)