Abstract:Computing paths in graph structures is a fundamental operation in a wide range of applications, from transportation networks to data analysis. The beer path problem, which captures the option of visiting points of interest, such as gas stations or convenience stops, prior to reaching the final destination, has been recently introduced and extensively studied in static graphs. However, existing approaches do not account for temporal information, which is often crucial in real-world scenarios. For instance, transit services may follow fixed schedules, and shops may only be accessible during certain hours.
In this work, we introduce the notion of beer paths in temporal graphs, where edges are time-dependent and certain vertices (beer vertices) are active only at specific time instances. We formally define the problems of computing earliest-arrival, latest-departure, fastest, and shortest temporal beer paths and propose efficient algorithms for these problems under both edge stream and adjacency list representations. The time complexity of each of our algorithms is aligned with that of corresponding temporal pathfinding algorithms, thus preserving efficiency.
Additionally, we present preprocessing techniques that enable efficient query answering under dynamic conditions, for example new openings or closings of shops. We achieve this through appropriate precomputation of selected paths or by transforming a temporal graph into an equivalent static graph.
From: Sotiris Kanellopoulos [view email]
[v1]
Fri, 11 Jul 2025 15:36:16 UTC (254 KB)
[v2]
Thu, 30 Oct 2025 21:31:26 UTC (393 KB)
[v3]
Mon, 6 Apr 2026 13:44:49 UTC (225 KB)
[v4]
Sun, 28 Jun 2026 14:21:45 UTC (226 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。