Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143460 | Operations Research Letters | 2006 | 8 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Adam Kasperski, Paweł Zieliński,