| Article ID: | iaor20061810 |
| Country: | Netherlands |
| Volume: | 34 |
| Issue: | 1 |
| Start Page Number: | 69 |
| End Page Number: | 76 |
| Publication Date: | Jan 2006 |
| Journal: | Operations Research Letters |
| Authors: | Kasperski Adam, Zielinski Pawel |
| Keywords: | graphs |
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.