arXiv Open Access 2023

Solving the recoverable robust shortest path problem in DAGs

Marcel Jackiewicz Adam Kasperski Pawel Zielinski

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DS

Penulis (3)

Marcel Jackiewicz

Adam Kasperski

Pawel Zielinski

Format Sitasi

APA MLA BibTeX

Jackiewicz, M., Kasperski, A., Zielinski, P. (2023). Solving the recoverable robust shortest path problem in DAGs. https://arxiv.org/abs/2309.02816

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2023
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓