{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T08:00:19Z","timestamp":1742976019499,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_34","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"433-444","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dynamic Tree Shortcut with Constant Degree"],"prefix":"10.1007","author":[{"given":"T-H. Hubert","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaowei","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenzi","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhichao","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"key":"34_CR1","unstructured":"Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical report (1987)"},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"Bagchi, A., Buchsbaum, A.L., Goodrich, M.T.: Biased skip lists. Algorithmica 42(1), 31\u201348 (2005)","DOI":"10.1007\/s00453-004-1138-6"},{"issue":"3","key":"34_CR3","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"W Samuel","year":"1985","unstructured":"Samuel, W.: Bent, Daniel D Sleator, and Robert E Tarjan. Biased search trees. SIAM Journal on Computing 14(3), 545\u2013568 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR4","unstructured":"Bodlaender, H.L., Tel, G., Santoro, N.: Trade-offs in non-reversing diameter. Nord. J. Comput. 1(1), 111\u2013134 (1994)"},{"key":"34_CR5","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":"34_CR6","doi-asserted-by":"crossref","unstructured":"Elkin, M., Solomon, S.: Optimal euclidean spanners: really short, thin and lanky. In: STOC, pp. 645\u2013654 (2013)","DOI":"10.1145\/2488608.2488691"},{"key":"34_CR7","unstructured":"Hesse, W.: Directed graphs requiring large numbers of shortcuts. In: SODA, pp. 665\u2013669 (2003)"},{"key":"34_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-642-16367-8_10","volume-title":"Property Testing","author":"S Raskhodnikova","year":"2010","unstructured":"Raskhodnikova, S.: Transitive-Closure Spanners: A Survey. In: Goldreich, O. (ed.) Property Testing. LNCS, vol. 6390, pp. 167\u2013196. Springer, Heidelberg (2010)"},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"34_CR10","doi-asserted-by":"crossref","unstructured":"Solomon, S.: From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics. In: STOC, pp. 363\u2013372 (2014)","DOI":"10.1145\/2591796.2591864"},{"key":"34_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-642-15775-2_5","volume-title":"Algorithms \u2013 ESA 2010","author":"S Solomon","year":"2010","unstructured":"Solomon, S., Elkin, M.: Balancing Degree, Diameter and Weight in Euclidean Spanners. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol. 6346, pp. 48\u201359. Springer, Heidelberg (2010)"},{"key":"34_CR12","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215\u2013225 (1975)","DOI":"10.1145\/321879.321884"},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"Thorup, M.: On shortcutting digraphs. In: Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1992, London, UK, pp. 205\u2013211. Springer (1993)","DOI":"10.1007\/3-540-56402-0_48"},{"issue":"1","key":"34_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1006\/jagm.1996.0829","volume":"23","author":"M Thorup","year":"1997","unstructured":"Thorup, M.: Parallel shortcutting of rooted trees. J. Algorithms 23(1), 139\u2013159 (1997)","journal-title":"J. Algorithms"},{"key":"34_CR15","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Space-time tradeoff for answering range queries (extended abstract). In: STOC, pp. 128\u2013136 (1982)","DOI":"10.1145\/800070.802185"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:26:36Z","timestamp":1676946396000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}