In this paper, we study weakly dynamic undirected graphs, and we propose an efficient polynomial algorithm that computes in advance alternative shortest paths for all possible configurations. No additional computation is then needed after any change in the problem because shortest paths are already known in all cases. We use these results to compute critical values for the traversal duration and to pre-compute best paths, and we apply this result to one delivery problem for trucks from one regional storehouse to several local stores when one possible point has a variable traversal duration.
Route planning in a weakly dynamic undirected graph
2013-05-01
968542 byte
Conference paper
Electronic Resource
English
Distributed IE for MASs with Undirected Graph
Springer Verlag | 2022
|Object-oriented undirected graph model in P&ID design system
British Library Online Contents | 2004
|Rotation-Matrix-Based Attitude Tracking Under an Undirected Tree Graph
Springer Verlag | 2022
|DYNAMIC ROUTE PLANNING DEVICE AND DYNAMIC ROUTE PLANNING METHOD
European Patent Office | 2024
|