Shortest paths with congruency constraints
| Témavezető: | Király Csaba |
| ELTE TTK, Operációkutatási Tsz. | |
| email: | csaba.kiraly@ttk.elte.hu |
Projekt leírás
It is known that the SHORTEST ODD PATH problem is NP-hard for conservative weights [1]. When the negative edges form a tree, a polynomial algorithm exists [2], furthermore, [2] also gave FPT algorithms with several parameters (number of negative edges, tree-width) to the problem. In this project, the goal is to give similar FPT algorithms to the SHORTEST q-MOD-m path problem.
Hivatkozások
[1] I. Schlotter, A. Sebő. Odd Paths, Cycles, and T-Joins: Connections and Algorithms. SIAM Journal on Discrete Mathematics. 39:484-504, 2025. doi:10.1137/23M158156X.
[2] A. Jüttner, Cs. Király, L.M. Mendoza-Cadena, Gy. Pap, I. Schlotter, Y. Yamaguchi. Shortest odd paths in undirected graphs with conservative weight functions. Discrete Applied Mathematics. 357:34-50, 2024. doi:10.1016/j.dam.2024.05.044.