On Cartesian trees and range minimum queries
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin / Heidelberg
2011
|
| Online Access: | http://hdl.handle.net/1721.1/61963 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1811088288007585792 |
|---|---|
| author | Demaine, Erik D. Landau, Gad M. Weimann, Oren |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Landau, Gad M. Weimann, Oren |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:59:50Z |
| format | Article |
| id | mit-1721.1/61963 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:59:50Z |
| publishDate | 2011 |
| publisher | Springer Berlin / Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/619632022-09-28T17:34:18Z On Cartesian trees and range minimum queries Demaine, Erik D. Landau, Gad M. Weimann, Oren Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Demaine, Erik D. Weimann, Oren 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. Israel Science Foundation (grant no. 35/05) Danish National Research Foundation. Center for Massive Data Algorithmics (MADALGO) Yahoo! Inc. 2011-03-25T15:21:18Z 2011-03-25T15:21:18Z 2009-07 2009-07 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-02926-4 http://hdl.handle.net/1721.1/61963 Demaine, Erik, Gad Landau, and Oren Weimann. “On Cartesian Trees and Range Minimum Queries.” Automata, Languages and Programming. Springer Berlin / Heidelberg, 2009. 341-353-353. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1007/978-3-642-02927-1_29 Automata, Languages and Programming. Proceedings of the 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Part I Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin / Heidelberg MIT web domain |
| spellingShingle | Demaine, Erik D. Landau, Gad M. Weimann, Oren On Cartesian trees and range minimum queries |
| title | On Cartesian trees and range minimum queries |
| title_full | On Cartesian trees and range minimum queries |
| title_fullStr | On Cartesian trees and range minimum queries |
| title_full_unstemmed | On Cartesian trees and range minimum queries |
| title_short | On Cartesian trees and range minimum queries |
| title_sort | on cartesian trees and range minimum queries |
| url | http://hdl.handle.net/1721.1/61963 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT demaineerikd oncartesiantreesandrangeminimumqueries AT landaugadm oncartesiantreesandrangeminimumqueries AT weimannoren oncartesiantreesandrangeminimumqueries |