期刊
OPERATIONS RESEARCH LETTERS
卷 31, 期 2, 页码 149-160出版社
ELSEVIER
DOI: 10.1016/S0167-6377(02)00192-X
关键词
shortest paths; reoptimization; flow algorithms
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. This situation is more general than 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. (C) 2002 Elsevier Science B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据