Refreshment of the shortest path cache with change of single edge
作者：
Highlights：
• We are the first to study the problem of refreshing a cache in a changed graph.
• A bitmap-based cache structure is designed to store shortest paths.
• Three algorithms are developed to detect affected shortest paths.
• Four refreshment strategies are proposed to update a cache efficiently.
• Extensive experiments on real data sets show the efficiency of our algorithms.
摘要
•We are the first to study the problem of refreshing a cache in a changed graph.•A bitmap-based cache structure is designed to store shortest paths.•Three algorithms are developed to detect affected shortest paths.•Four refreshment strategies are proposed to update a cache efficiently.•Extensive experiments on real data sets show the efficiency of our algorithms.
论文关键词：Shortest path caching,Cache refreshment strategy,Change of road network,Affected shortest paths
论文评审过程：Received 1 December 2014, Revised 30 July 2016, Accepted 2 August 2016, Available online 3 August 2016, Version of Record 22 September 2016.
论文官网地址：https://doi.org/10.1016/j.eswa.2016.08.011
