{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:36Z","timestamp":1740109296682,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2018,2,2]],"date-time":"2018-02-02T00:00:00Z","timestamp":1517529600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001804","name":"Canada Research Chairs","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001804","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s00453-018-0413-x","type":"journal-article","created":{"date-parts":[[2018,2,2]],"date-time":"2018-02-02T10:19:17Z","timestamp":1517566757000},"page":"3728-3765","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dynamic Path Queries in Linear Space"],"prefix":"10.1007","volume":"80","author":[{"given":"Meng","family":"He","sequence":"first","affiliation":[]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[]},{"given":"Gelin","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,2,2]]},"reference":[{"key":"413_CR1","unstructured":"Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical Reports on Tel Aviv University (1987)"},{"key":"413_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/3-540-45022-X_8","volume-title":"Automata, Languages and Programming","author":"Stephen Alstrup","year":"2000","unstructured":"Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Proceedings of the 27th International Colloquium on Automata, Languages and Programming, ICALP 2000, Geneva, Switzerland, July 9\u201315, pp. 73\u201384 (2000)"},{"key":"413_CR3","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: 39th Annual Symposium on Foundations of Computer Science, FOCS \u201998, Palo Alto, California, USA, November 8\u201311, pp. 534\u2013544 (1998)","DOI":"10.1109\/SFCS.1998.743504"},{"issue":"6","key":"413_CR4","doi-asserted-by":"publisher","first-page":"1488","DOI":"10.1137\/S009753970240481X","volume":"32","author":"L Arge","year":"2003","unstructured":"Arge, L., Vitter, J.S.: Optimal external memory interval management. SIAM J. Comput. 32(6), 1488\u20131508 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"413_CR5","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P Bille","year":"2005","unstructured":"Bille, P.: A survey on tree edit distance and related problems. Theor. Comput. Sci. 337(1\u20133), 217\u2013239 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"413_CR6","unstructured":"Blelloch, G.E.: Space-efficient dynamic orthogonal point location, segment intersection, and range reporting. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20\u201322, pp. 894\u2013903 (2008)"},{"key":"413_CR7","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-642-33090-2_20","volume-title":"Algorithms \u2013 ESA 2012","author":"Gerth St\u00f8lting Brodal","year":"2012","unstructured":"Brodal, G.S., Davoodi, P., Lewenstein, M., Raman, R., Rao, S.S.: Two dimensional range minimum queries and fibonacci lattices. In: Proceedings of the 20th Annual European Symposium on Algorithms, ESA 2012, Ljubljana, Slovenia, September 10\u201312, pp. 217\u2013228 (2012)"},{"key":"413_CR8","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: Path minima queries in dynamic weighted trees. In: Proceedings of the 12th International Symposium Workshop on Algorithms and Data Structures, WADS 2011, New York, NY, USA, August 15\u201317, pp. 290\u2013301 (2011)","DOI":"10.1007\/978-3-642-22300-6_25"},{"issue":"24","key":"413_CR9","doi-asserted-by":"publisher","first-page":"2588","DOI":"10.1016\/j.tcs.2010.05.003","volume":"412","author":"GS Brodal","year":"2011","unstructured":"Brodal, G.S., Gfeller, B., J\u00f8rgensen, A.G., Sanders, P.: Towards optimal range medians. Theor. Comput. Sci. 412(24), 2588\u20132601 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"413_CR10","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/978-3-662-44777-2_21","volume-title":"Algorithms - ESA 2014","author":"Timothy M. Chan","year":"2014","unstructured":"Chan, T.M., He, M., Munro, J.I., Zhou, G.: Succinct indices for path minimum, with applications to path reporting. In: Proceedings of the 22th Annual European Symposium on Algorithms, ESA 2014, Wroclaw, Poland, September 8\u201310, pp. 247\u2013259 (2014)"},{"key":"413_CR11","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF01840366","volume":"2","author":"B Chazelle","year":"1987","unstructured":"Chazelle, B.: Computing on a free tree via complexity-preserving mappings. Algorithmica 2, 337\u2013361 (1987)","journal-title":"Algorithmica"},{"key":"413_CR12","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"issue":"3","key":"413_CR13","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/s00453-012-9683-x","volume":"68","author":"ED Demaine","year":"2014","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On cartesian trees and range minimum queries. Algorithmica 68(3), 610\u2013625 (2014)","journal-title":"Algorithmica"},{"issue":"4","key":"413_CR14","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"GN Frederickson","year":"1985","unstructured":"Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14(4), 781\u2013798 (1985)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"413_CR15","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1137\/S0097539792226825","volume":"26","author":"GN Frederickson","year":"1997","unstructured":"Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput. 26(2), 484\u2013538 (1997)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"413_CR16","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jagm.1996.0835","volume":"24","author":"GN Frederickson","year":"1997","unstructured":"Frederickson, G.N.: A data structure for dynamically maintaining rooted trees. J. Algorithms 24(1), 37\u201365 (1997)","journal-title":"J. Algorithms"},{"key":"413_CR17","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-16321-0_35","volume-title":"String Processing and Information Retrieval","author":"Meng He","year":"2010","unstructured":"He, M., Munro, J.I.: Succinct representations of dynamic strings. In: Proceedings of the 17th International Symposium on String Processing and Information Retrieval, SPIRE 2010, Los Cabos, Mexico, October 11\u201313, pp. 334\u2013346 (2010)"},{"issue":"2","key":"413_CR18","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1016\/j.comgeo.2013.08.007","volume":"47","author":"M He","year":"2014","unstructured":"He, M., Munro, J.I.: Space efficient data structures for dynamic orthogonal range counting. Comput. Geom. 47(2), 268\u2013281 (2014)","journal-title":"Comput. Geom."},{"key":"413_CR19","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-642-25591-5_18","volume-title":"Algorithms and Computation","author":"Meng He","year":"2011","unstructured":"He, M., Munro, J.I., Nicholson, P.K.: Dynamic range selection in linear space. In: Proceedings of the 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan, December 5\u20138, pp. 160\u2013169 (2011)"},{"issue":"4","key":"413_CR20","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/2344422.2344432","volume":"8","author":"M He","year":"2012","unstructured":"He, M., Munro, J.I., Rao, S.S.: Succinct ordinal trees based on tree covering. ACM Trans. Algorithms 8(4), 42 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"413_CR21","doi-asserted-by":"crossref","unstructured":"He, M., Munro, J.I., Zhou, G.: Path queries in weighted trees. In: Proceedings of the 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan, December 5\u20138, pp. 140\u2013149 (2011)","DOI":"10.1007\/978-3-642-25591-5_16"},{"key":"413_CR22","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/978-3-642-33090-2_50","volume-title":"Algorithms \u2013 ESA 2012","author":"Meng He","year":"2012","unstructured":"He, M., Munro, J.I., Zhou, G.: Succinct data structures for path queries. In: Proceedings of the 20th Annual European Symposium on Algorithms, ESA 2012, Ljubljana, Slovenia, September 10\u201312, pp. 575\u2013586 (2012)"},{"key":"413_CR23","first-page":"565","volume-title":"Algorithms and Computation","author":"Meng He","year":"2014","unstructured":"He, M., Munro, J.I., Zhou, G.: Dynamic path counting and reporting in linear space. In: Proceedings of the 25th International Symposium on Algorithms and Computation, ISAAC 2014, Jeonju, Korea, December 15\u201317, pp. 565\u2013577 (2014)"},{"issue":"4","key":"413_CR24","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1007\/s00453-014-9894-4","volume":"70","author":"M He","year":"2014","unstructured":"He, M., Munro, J.I., Zhou, G.: A framework for succinct labeled ordinal trees over large alphabets. Algorithmica 70(4), 696\u2013717 (2014)","journal-title":"Algorithmica"},{"key":"413_CR25","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Shafrir, N.: Path minima in incremental unrooted trees. In: Proceedings of the 16th Annual European Symposium on Algorithms, ESA 2008, Karlsruhe, Germany, September 15\u201317, pp. 565\u2013576 (2008)","DOI":"10.1007\/978-3-540-87744-8_47"},{"issue":"1","key":"413_CR26","first-page":"1","volume":"12","author":"D Krizanc","year":"2005","unstructured":"Krizanc, D., Morin, P., Smid, M.H.M.: Range mode and range median queries on lists and trees. Nord. J. Comput. 12(1), 1\u201317 (2005)","journal-title":"Nord. J. Comput."},{"issue":"3","key":"413_CR27","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"JI Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"key":"413_CR28","unstructured":"Muthukrishnan, S., M\u00fcller, M.: Time and space efficient method-lookup for object-oriented programs (extended abstract). In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996, Atlanta, Georgia, USA, January 28\u201330, pp. 42\u201351 (1996)"},{"issue":"5","key":"413_CR29","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1137\/130908245","volume":"43","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. SIAM J. Comput. 43(5), 1781\u20131806 (2014)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"413_CR30","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/2601073","volume":"10","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"413_CR31","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.comgeo.2008.09.001","volume":"42","author":"Y Nekrich","year":"2009","unstructured":"Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. Comput. Geom. 42(4), 342\u2013351 (2009)","journal-title":"Comput. Geom."},{"key":"413_CR32","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.jda.2012.08.003","volume":"17","author":"M Patil","year":"2012","unstructured":"Patil, M., Shah, R., Thankachan, S.V.: Succinct representations of weighted trees supporting path queries. J. Discrete Algorithms 17, 103\u2013108 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"413_CR33","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M P\u01cetra\u015fcu","year":"2006","unstructured":"P\u01cetra\u015fcu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35(4), 932\u2013963 (2006)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"413_CR34","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007). https:\/\/doi.org\/10.1145\/1290672.1290680","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0413-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0413-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0413-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,10]],"date-time":"2019-10-10T02:02:55Z","timestamp":1570672975000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0413-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,2]]},"references-count":34,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["413"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0413-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,2,2]]},"assertion":[{"value":"27 August 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}