Preprint: not peer reviewed. Results may change in later versions.
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.
Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.
Record
- Archive ID
- arxiv:2309.02816
- Published
- Sep 6, 2023
- arXiv
- 2309.02816
- Categories
- cs.DS
- Provenance
- arxiv