A new algorithm for reoptimizing shortest paths when the arc costs change

A new algorithm for reoptimizing shortest paths when the arc costs change

0.00 Avg rating0 Votes
Article ID: iaor2004380
Country: Netherlands
Volume: 31
Issue: 2
Start Page Number: 149
End Page Number: 160
Publication Date: Mar 2003
Journal: Operations Research Letters
Authors: ,
Keywords: combinatorial analysis, graphs
Abstract:

We propose the first algorithmic approach which reoptimizes the shortest paths when any subset of arcs of the input graph is affected by a change of the costs, which can be either lower or higher than the old ones. The situation is more general then the ones addressed in the literature so far. We analyze the worst-case time complexity of the algorithm as a function of both the input size and the overall cost perturbation, and discuss cases for which the proposed reoptimization method theoretically outperforms the approach of applying a standard shortest path algorithm after the change of the arc costs.

Reviews

Required fields are marked *. Your email address will not be published.