Projects per year
Abstract
An instance of the NPhard 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 higherorder shortest path problem.
Original language  English 

Number of pages  24 
Journal  Mathematical Programming 
Volume  2024 
Early online date  2024 
DOIs  
Publication status  Epub ahead of print  2024 
Keywords
 68Q25 Analysis of algorithms and problem complexity
 90C20 Quadratic programming
 90C27 Combinatorial optimization
 90C35 Programming involving graphs or networks
 Higherorder shortest path problem
 Linearization
 Quadratic shortest path problem
ASJC Scopus subject areas
 Software
 General Mathematics
Fields of Expertise
 Information, Communication & Computing
Fingerprint
Dive into the research topics of 'A linear time algorithm for linearizing quadratic and higherorder shortest path problems'. Together they form a unique fingerprint.Projects
 1 Finished

Doctoral Program: Discrete Mathematics
Ebner, O., Lehner, F., Greinecker, F., Burkard, R., Wallner, J., Elsholtz, C., Woess, W., Raseta, M., Bazarova, A., Krenn, D., Lehner, F., Kang, M., Tichy, R., SavaHuss, E., Klinz, B., Heuberger, C., Grabner, P., Barroero, F., Cuno, J., Kreso, D., Berkes, I. & Kerber, M.
1/05/10 → 30/06/24
Project: Research project