Parameterized Complexity of Finding Dissimilar Shortest Paths

Ryo Funayama, Yasuaki Kobayashi, Takeaki Uno

We consider the problem of finding ``dissimilar'' $k$ shortest paths from $s$ to $t$ in an edge-weighted directed graph $D$, where the dissimilarity is measured by the minimum pair…