The Taub Faculty of Computer Science Events and Talks

Consider planning a trip in a train network. In contrast to, say, a road network, the edges are temporal, i.e., they are only available at certain times. Another important difficulty is that trains, unfortunately, sometimes get delayed. This is especially bad if it causes one to miss subsequent trains. The best way to prepare against this is to have a connection that is robust to some number of (small) delays. An important factor in determining the robustness of a connection is how far in advance delays are announced and whether deviating from the initial route is possible. We analyse three settings: – All delays are known before departure. – Delays may be occurring without prior warning. – Deviating from the route is not possible. (In this case it does not make any difference whether delays are known before departure or occur during the travel.) We provide a (parameterized) complexity analysis of all three cases. Based on joint work with Eugen Füchsle, Rolf Niedermeier, and Malte Renken.