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

被引：32

作者：

Kasperski, A

Zielinski, P

机构：

[1] Wroclaw Univ Technol, Inst Ind Engn & Management, PL-50370 Wroclaw, Poland

[2] Wroclaw Univ Technol, Inst Math, PL-50370 Wroclaw, Poland

来源：

OPERATIONS RESEARCH LETTERS | 2006年 / 34卷 / 01期

关键词：

robust optimization; NP-hardness; pseudopolynomial algorithm; shortest path problem; combinatorial optimization;

D O I：

10.1016/j.orl.2005.01.008

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：69 / 76

页数：8

共 11 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] Interval data minmax regret network optimization problems [J].