{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:50:34Z","timestamp":1780822234570,"version":"3.54.1"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,12,15]],"date-time":"2022-12-15T00:00:00Z","timestamp":1671062400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,15]],"date-time":"2022-12-15T00:00:00Z","timestamp":1671062400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["USRA - 551540 - 2020"],"award-info":[{"award-number":["USRA - 551540 - 2020"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00453-022-01045-4","type":"journal-article","created":{"date-parts":[[2022,12,15]],"date-time":"2022-12-15T14:09:24Z","timestamp":1671113364000},"page":"1679-1705","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Shortest Beer Path Queries in Outerplanar Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6202-816X","authenticated-orcid":false,"given":"Joyce","family":"Bacic","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saeed","family":"Mehrabi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,12,15]]},"reference":[{"key":"1045_CR1","unstructured":"Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical Report 71\/87, Tel-Aviv University, (1987)"},{"key":"1045_CR2","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of the 4th Latin American Symposium on Theoretical Informatics, volume 1776 of Lecture Notes in Computer Science, pp. 88\u201394. Springer, Berlin (2000)","DOI":"10.1007\/10719839_9"},{"issue":"2","key":"1045_CR3","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s00453-016-0170-7","volume":"78","author":"TM Chan","year":"2017","unstructured":"Chan, T.M., He, M., Munro, J.I., Zhou, G.: Succinct indices for path minimum, with applications. Algorithmica 78(2), 453\u2013491 (2017)","journal-title":"Algorithmica"},{"key":"1045_CR4","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":"1045_CR5","doi-asserted-by":"crossref","unstructured":"Djidjev, H., Pantziou, G.E., Zaroliagis, C.D.: Computing shortest paths and distances in planar graphs. In: Automata, Languages and Programming, 18th International Colloquium, ICALP91, volume 510 of Lecture Notes in Computer Science, pp. 327\u2013338. Springer (1991)","DOI":"10.1007\/3-540-54233-7_145"},{"issue":"2","key":"1045_CR6","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1045_CR7","doi-asserted-by":"publisher","first-page":"47","DOI":"10.7155\/jgaa.00082","volume":"8","author":"A Maheshwari","year":"2004","unstructured":"Maheshwari, A., Zeh, N.: I\/o-optimal algorithms for outerplanar graphs. J. Graph Algorithms Appl. 8(1), 47\u201387 (2004)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"1045_CR8","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 26(2), 207\u2013230 (2006)","journal-title":"Combinatorica"},{"key":"1045_CR9","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1006\/jagm.1996.0829","volume":"32","author":"M Thorup","year":"1997","unstructured":"Thorup, M.: Parallel shortcutting of rooted trees. J. Algorithms 32, 139\u2013159 (1997)","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01045-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01045-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01045-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,27]],"date-time":"2023-05-27T03:34:50Z","timestamp":1685158490000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01045-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,15]]},"references-count":9,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1045"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01045-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,15]]},"assertion":[{"value":"1 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}