2026-08-16T16:18:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19337 2024-03-06T11:03:48Z ddc:004 open_access

Shortest Beer Path Queries in Digraphs with Bounded Treewidth Gudmundsson, Joachim Sha, Yuan Graph algorithms Shortest Path Data structures Bounded treewidth A beer digraph G is a real-valued weighted directed graph where some of the vertices have beer stores. A beer path from a vertex u to a vertex v in G is a path in G from u to v that visits at least one beer store. In this paper we consider the online shortest beer path query in beer digraphs with bounded treewidth t. Assume that a tree decomposition of treewidth t on a beer digraph with n vertices is given. We show that after O(t³n) time preprocessing on the beer digraph, (i) a beer distance query can be answered in O(t³α(n)) time, where α(n) is the inverse Ackermann function, and (ii) a shortest beer path can be reported in O(t³α(n)L) time, where L is the number of edges on the path. In the process we show an improved O(t³α(n)L) time shortest path query algorithm, compared with the currently best O(t⁴α(n)L) time algorithm [Chaudhuri & Zaroliagis, 2000]. We also consider queries in a dynamic setting where the weight of an edge in G can change over time. We show two data structures. Assume t is constant and let β be any constant in (0,1). The first data structure uses O(n) preprocessing time, answers a beer distance query in O(α(n)) time and reports a shortest beer path in O(α(n) L) time. It can be updated in O(n^β) time after an edge weight change. The second data structure has O(n) preprocessing time, answers a beer distance query in O(log n) time, reports a shortest beer path in O(log n + L) time, and can be updated in O(log n) time after an edge weight change. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joachim Gudmundsson and Yuan Sha 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.35 urn:nbn:de:0030-drops-193379 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.35 eng https://creativecommons.org/licenses/by/4.0/legalcode