标题： 啤酒路径问题在时序图中 显示英文标题

标题： Beer Path Problems in Temporal Graphs

摘要： 在图结构中计算路径是许多应用中的基本操作，从交通网络到数据分析。啤酒路径问题，即在到达最终目的地之前访问兴趣点（如加油站或便利停靠点）的选项，最近在静态图中被引入并进行了广泛研究。然而，现有方法没有考虑时间信息，这在现实场景中通常是至关重要的。例如，公共交通服务可能遵循固定的时刻表，而商店可能只在特定时间段内可访问。在本工作中，我们引入了时间图中的啤酒路径概念，其中边是时间依赖的，某些顶点（啤酒顶点）仅在特定时间实例处于活动状态。我们正式定义了计算最早到达、最晚出发、最快和最短时间啤酒路径的问题，并提出了在边流和邻接表表示下解决这些问题的高效算法。我们每个算法的时间复杂度与相应的时间路径查找算法一致，从而保持了效率。此外，我们提出了预处理技术，使在动态条件下能够高效回答查询，例如商店的新开放或关闭。我们通过适当的选定路径预计算或通过将时间图转换为等效静态图来实现这一点。 显示英文摘要

摘要： 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.