Shortest odd paths in undirected graphs
with conservative weight functions
Alpár Jüttner, Csaba Király, Lydia Mirabel Mendoza-Cadena,
Gyula Pap, Ildikó Schlotter, Yutaro Yamaguchi
Highlights
- The problem with conservative weights and negative edges forming a tree is in P.
- FPT algorithm with parameter the number of negative edges (conservativeness assumed).
FPT algorithm with parameter treewidth.
Keywords: Shortest odd path, Parity constrained odd path, Fixed-parameter algorithms, Treewidth, Monadic second-order logic
