ICS Theory Group

Spring 2016: Theory Seminar
DBH, Room 1423, 1:00pm

May 20, 2016:

A Sidetrack-based Approach for the k Shortest Simple Path Problem

Denis Kurz

We propose an algorithm for the problem of finding the k shortest simple s-t paths in a directed, weighted graph. Unlike other algorithms for this problem, it does not solve the replacement path problem repeatedly. Instead, we exploit the notion of sidetracks of a shortest path trees. Sidetracks were first used by Eppstein to solve a similar problem where the output paths are not required to be simple.

Our algorithm maintains the worst case running time of state-of-the-art algorithms for this problem. In practice, the sidetrack-based approach is highly competitive on all graph classes that we used in computational studies compared to other approaches, and faster by up to two orders of magnitude on some of the classes.

Joint work with Petra Mutzel