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. We give polynomial-time algorithms for the two extreme cases: delays known before departure and delays occurring without prior warning (the latter leading to a two-player game scenario). Interestingly, in the latter case, we show that the problem becomes PSPACE-complete if the itinerary is demanded to be a path.
翻译:考虑在火车网络中规划行程。 相比之下, 道路网络, 边缘是时间性的, 也就是说, 只在特定时间可以使用 。 另一个重要的困难是火车, 不幸的是, 有时会延误。 如果这导致一个后来的火车错过了火车, 情况就特别糟糕。 最好的防范方法是建立连接, 与一些( 小)的延误保持紧密联系。 确定连接是否稳健的一个重要因素是提前多少时间宣布延迟。 我们给两个极端案例给出了多时制算法: 出发前已知的延迟和在没有事先警告的情况下发生的延误( 后者导致一场双人游戏 ) 。 有趣的是, 在后一种情况下, 我们证明如果行程被要求成为一条路径, 问题就已经完全完成 PSPACE 。