{"id":"arxiv:2309.02816","kind":"preprint","title":"Solving the recoverable robust shortest path problem in DAGs","authors":["Marcel Jackiewicz","Adam Kasperski","Pawel Zielinski"],"author_count":3,"year":2023,"published":"2023-09-06","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2309.02816","nct_id":null,"source_url":"https://arxiv.org/abs/2309.02816","archive_url":"https://space-kitty.com/papers/arxiv:2309.02816","updated":"2023-09-06","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2309.02816","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"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.","topics":[],"cited_in_dossiers":[]}