2026-07-22T21:28:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15495 2024-03-06T10:55:26Z ddc:004 open_access

Shortest Beer Path Queries in Outerplanar Graphs Bacic, Joyce Mehrabi, Saeed Smid, Michiel shortest paths outerplanar graph A beer graph is an undirected graph G, in which each edge has a positive weight and some vertices have a beer store. A beer path between two vertices u and v in G is any path in G between u and v that visits at least one beer store. We show that any outerplanar beer graph G with n vertices can be preprocessed in O(n) time into a data structure of size O(n), such that for any two query vertices u and v, (i) the weight of the shortest beer path between u and v can be reported in O(α(n)) time (where α(n) is the inverse Ackermann function), and (ii) the shortest beer path between u and v can be reported in O(L) time, where L is the number of vertices on this path. Both results are optimal, even when G is a beer tree (i.e., a beer graph whose underlying graph is a tree). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joyce Bacic and Saeed Mehrabi and Michiel Smid 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.62 urn:nbn:de:0030-drops-154950 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.62 eng https://creativecommons.org/licenses/by/4.0/legalcode