6533b7cffe1ef96bd1258d09
RESEARCH PRODUCT
The computational complexity of the relative robust shortest path problem with interval data
Paweł Zielińskisubject
Discrete mathematicsInformation Systems and ManagementGeneral Computer ScienceManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringLongest path problemWidest path problemEuclidean shortest pathShortest Path Faster AlgorithmTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYModeling and SimulationShortest path problemK shortest path routingCanadian traveller problemDistanceMathematicsofComputing_DISCRETEMATHEMATICSMathematicsdescription
Abstract The paper deals with the relative robust shortest path problem in a directed arc weighted graph, where arc lengths are specified as intervals containing possible realizations of arc lengths. The complexity status of this problem has been unknown in the literature. We show that the problem is NP -hard.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2004-11-01 | European Journal of Operational Research |