Solving the Recoverable Robust Shortest Path Problem in DAGs

Marcel Jackiewicz (), Adam Kasperski () and Paweł Zieliński ()
Additional contact information
Marcel Jackiewicz: Wrocław University of Science and Technology
Adam Kasperski: Wrocław University of Science and Technology
Paweł Zieliński: Wrocław University of Science and Technology

Chapter Chapter 21 in Operations Research Proceedings 2023, 2025, pp 161-167 from Springer

Abstract: Abstract This paper deals with the recoverable robust shortest path problem under the interval uncertainty representation. The problem is known to be strongly NP-hard and not approximable in general digraphs. Polynomial-time algorithms for the problem under consideration in DAGs are proposed.

Keywords: Robust optimization; Interval uncertainty; Shortest path (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-58405-3_21

Ordering information: This item can be ordered from
http://www.springer.com/9783031584053

DOI: 10.1007/978-3-031-58405-3_21

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().