{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T10:24:44Z","timestamp":1794392684485,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642222993","type":"print"},{"value":"9783642223006","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22300-6_25","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T08:41:31Z","timestamp":1312879291000},"page":"290-301","source":"Crossref","is-referenced-by-count":14,"title":["Path Minima Queries in Dynamic Weighted Trees"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pooya","family":"Davoodi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Srinivasa Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"25_CR1","unstructured":"Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical report, Department of Computer Science, School of Mathematical Sciences, Tel Aviv University (1987)"},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/3-540-45022-X_8","volume-title":"Automata, Languages and Programming","author":"S. Alstrup","year":"2000","unstructured":"Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 73\u201384. Springer, Heidelberg (2000)"},{"key":"25_CR3","first-page":"534","volume-title":"Proc. 39th Annual Symposium on Foundations of Computer Science","author":"S. Alstrup","year":"1998","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proc. 39th Annual Symposium on Foundations of Computer Science, p. 534. IEEE Computer Society, Washington, DC, USA (1998)"},{"issue":"4","key":"25_CR4","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0020-0190(97)00170-1","volume":"64","author":"S. Alstrup","year":"1997","unstructured":"Alstrup, S., Secher, J., Spork, M.: Optimal on-line decremental connectivity in trees. Information Processing Letters\u00a064(4), 161\u2013164 (1997)","journal-title":"Information Processing Letters"},{"issue":"3","key":"25_CR5","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/j.comgeo.2004.04.003","volume":"29","author":"P. Bose","year":"2004","unstructured":"Bose, P., Maheshwari, A., Narasimhan, G., Smid, M., Zeh, N.: Approximating geometric bottleneck shortest paths. Computational Geometry\u00a029(3), 233\u2013249 (2004)","journal-title":"Computational Geometry"},{"issue":"4","key":"25_CR6","first-page":"337","volume":"3","author":"G.S. Brodal","year":"1996","unstructured":"Brodal, G.S., Chaudhuri, S., Radhakrishnan, J.: The randomized complexity of maintaining the minimum. Nordic Journal of Computing\u00a03(4), 337\u2013351 (1996)","journal-title":"Nordic Journal of Computing"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. Algorithmica, Special issue on ESA 2010 (2011) (in press)","DOI":"10.1007\/978-3-642-15781-3_15"},{"key":"25_CR8","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\u00a02, 337\u2013361 (1987)","journal-title":"Algorithmica"},{"issue":"4","key":"25_CR9","doi-asserted-by":"publisher","first-page":"894","DOI":"10.1137\/S0097539700370539","volume":"34","author":"R. Cole","year":"2005","unstructured":"Cole, R., Hariharan, R.: Dynamic lca queries on trees. SIAM Journal on Computing\u00a034(4), 894\u2013923 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-642-02927-1_29","volume-title":"Automata, Languages and Programming","author":"E.D. Demaine","year":"2009","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On cartesian trees and range minimum queries. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 341\u2013353. Springer, Heidelberg (2009)"},{"issue":"4","key":"25_CR11","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G.N. Frederickson","year":"1985","unstructured":"Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing\u00a014(4), 781\u2013798 (1985)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"25_CR12","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Journal of Computer and System Sciences\u00a048(3), 533\u2013551 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR13","first-page":"135","volume-title":"Proc. 16th Annual ACM Symposium on Theory of Computing","author":"H.N. Gabow","year":"1984","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. 16th Annual ACM Symposium on Theory of Computing, pp. 135\u2013143. ACM Press, New York (1984)"},{"key":"25_CR14","first-page":"185","volume-title":"Proc. 17th Annual ACM Symposium on Theory of Computing","author":"D. Harel","year":"1985","unstructured":"Harel, D.: A linear time algorithm for finding dominators in flow graphs and related problems. In: Proc. 17th Annual ACM Symposium on Theory of Computing, pp. 185\u2013194. ACM Press, New York (1985)"},{"key":"25_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/978-3-540-87744-8_47","volume-title":"Algorithms - ESA 2008","author":"H. Kaplan","year":"2008","unstructured":"Kaplan, H., Shafrir, N.: Path minima in incremental unrooted trees. In: Halperin, D., Mehlhorn, K. (eds.) Esa 2008. LNCS, vol.\u00a05193, pp. 565\u2013576. Springer, Heidelberg (2008)"},{"key":"25_CR16","first-page":"573","volume-title":"Proc. 34th Annual ACM Symposium on Theory of Computing","author":"H. Kaplan","year":"2002","unstructured":"Kaplan, H., Shafrir, N., Tarjan, R.E.: Meldable heaps and boolean union-find. In: Proc. 34th Annual ACM Symposium on Theory of Computing, pp. 573\u2013582. ACM Press, New York (2002)"},{"issue":"2","key":"25_CR17","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02526037","volume":"18","author":"V. King","year":"1997","unstructured":"King, V.: A simpler minimum spanning tree verification algorithm. Algorithmica\u00a018(2), 263\u2013270 (1997)","journal-title":"Algorithmica"},{"key":"25_CR18","unstructured":"Neto, D.M.: Efficient cluster compensation for lin-kernighan heuristics. PhD thesis. University of Toronto, Toronto, Ontario, Canada (1999)"},{"key":"25_CR19","unstructured":"Nivasch, G.: Inverse ackermann without pain (2009), http:\/\/www.yucs.org\/~gnivasch\/alpha\/"},{"issue":"4","key":"25_CR20","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 Journal on Computing\u00a035(4), 932\u2013963 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"25_CR21","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s00493-006-0014-1","volume":"26","author":"S. Pettie","year":"2006","unstructured":"Pettie, S.: An inverse-ackermann type lower bound for online minimum spanning tree verification. Combinatorica\u00a026(2), 207\u2013230 (2006)","journal-title":"Combinatorica"},{"issue":"3","key":"25_CR22","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. Sleator","year":"1983","unstructured":"Sleator, D., Endre Tarjan, R.: A data structure for dynamic trees. Journal of Computer and System Sciences\u00a026(3), 362\u2013391 (1983)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"25_CR23","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"R.E. Tarjan","year":"1979","unstructured":"Tarjan, R.E.: Applications of path compression on balanced trees. J. ACM\u00a026(4), 690\u2013715 (1979)","journal-title":"J. ACM"},{"issue":"4","key":"25_CR24","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J. Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Communications of the ACM\u00a023(4), 229\u2013239 (1980)","journal-title":"Communications of the ACM"},{"key":"25_CR25","first-page":"128","volume-title":"Proc. 14th Annual ACM Symposium on Theory of Computing","author":"A.C.-C. Yao","year":"1982","unstructured":"Yao, A.C.-C.: Space-time tradeoff for answering range queries (extended abstract). In: Proc. 14th Annual ACM Symposium on Theory of Computing, pp. 128\u2013136. ACM Press, New York (1982)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22300-6_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T18:54:20Z","timestamp":1560452060000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22300-6_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642222993","9783642223006"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22300-6_25","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-642-22300-6","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}