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 captures the option of visiting points of interest, such as gas stations or convenience stops, prior to reaching the final destination. Despite extensive studies in static graphs, existing approaches do not account for temporal information, which is 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 only active 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.
Blogger's Review: This study offers a fresh perspective on pathfinding problems in temporal graphs, particularly the effectiveness of considering time factors in dynamic environments, showcasing its potential in real-world applications. The introduced preprocessing techniques lay the groundwork for further real-time queries, warranting deeper exploration in transportation and service sectors.