Projects per year
Abstract
The quadratic shortest path problem (QSPP) in a directed graph asks for a directed path from a given source vertex to a given sink vertex, so that the sum of the interaction costs over all pairs of arcs on the path is minimized. We consider special cases of the QSPP that are linearizable as a shortest path problem in the sense of Bookhold. If the QSPP on a directed graph is linearizable under all possible choices of the arc interaction costs, the graph is called universally linearizable.
We provide various combinatorial characterizations of universally linearizable graphs that are centered around the structure of sourcetosink paths and around certain forbidden subgraphs. Our characterizations lead to fast and simple recognition algorithms for universally linearizable graphs. Furthermore, we establish the intractability of deciding whether a concrete instance of the QSPP (with a given graph and given arc interaction costs) is linearizable.
We provide various combinatorial characterizations of universally linearizable graphs that are centered around the structure of sourcetosink paths and around certain forbidden subgraphs. Our characterizations lead to fast and simple recognition algorithms for universally linearizable graphs. Furthermore, we establish the intractability of deciding whether a concrete instance of the QSPP (with a given graph and given arc interaction costs) is linearizable.
Original language  English 

Title of host publication  GraphTheoretic Concepts in Computer Science 
Subtitle of host publication  WG 2021 
Editors  Łukasz Kowalik, Michał Pilipczuk, Pawel Rzążewski 
Publisher  Springer 
Pages  245256 
Number of pages  12 
ISBN (Print)  9783030868376 
DOIs  
Publication status  Published  20 Sept 2021 
Event  47th International Workshop on GraphTheoretic Concepts in Computer Science: WG 2021  Warsaw, Poland Duration: 23 Jun 2021 → 25 Jun 2021 
Publication series
Name  Springer Lecture Notes in Computer Science 

Publisher  Springer 
Volume  12911 
Conference
Conference  47th International Workshop on GraphTheoretic Concepts in Computer Science 

Abbreviated title  WG 2021 
Country/Territory  Poland 
City  Warsaw 
Period  23/06/21 → 25/06/21 
Keywords
 quadratic shortest path problem
 linearizable instances
 Computational complexity
 special cases
ASJC Scopus subject areas
 Mathematics(all)
Fields of Expertise
 Information, Communication & Computing
Treatment code (Nähere Zuordnung)
 Basic  Fundamental (Grundlagenforschung)
Fingerprint
Dive into the research topics of 'Linearizable Special Cases of the Quadratic Shortest Path Problem'. Together they form a unique fingerprint.Projects
 1 Active

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