The robust shortest path problem in series-parallel multidigraphs with interval data

摘要

In this paper the robust shortest path problem in edge series-parallel multidigraphs with interval costs is examined. The maximal regret criterion is applied to calculate the optimal solution. It is shown that this problem is NP-hard. A pseudopolynomial algorithm for the studied problem is constructed. (c) 2005 Elsevier B.V. All rights reserved.