@inproceedings{36cd64f27fab49dcbbea4ccd18c18cf0,
title = "A linear time algorithm for linearizing quadratic and higher-order shortest path problems",
abstract = "An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best algorithm. The algorithm is based on a new insight revealing that the linearizability of the QSPP for acyclic digraphs can be seen as a local property. Our approach extends to the more general higher-order shortest path problem.",
keywords = "higher-order shortest path problem, linearization, quadratic shortest path problem",
author = "{\c C}ela , {Eranda } and Bettina Klinz and Stefan Lendl and Woeginger, {Gerhard J.} and Lasse Wulf",
year = "2023",
doi = "10.1007/978-3-031-32726-1_33",
language = "English",
isbn = "978-3-031-32725-4",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "466--479",
editor = "{Del Pia}, Alberto and Volker Kaibel",
booktitle = "Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings",
note = "24th Conference on Integer Programming and Combinatorial Optimization : IPCO 2023, IPCO 2023 ; Conference date: 21-06-2023 Through 23-06-2023",
}