论文标题
时间连通性：应对预见和不可预见的延迟
Temporal Connectivity: Coping with Foreseen and Unforeseen Delays
论文作者
论文摘要
考虑计划在火车网络中进行旅行。与道路网络相反，边缘是暂时的，即它们仅在某些时间可用。另一个重要的困难是，不幸的是，火车有时会被延迟。如果这会导致人们错过随后的火车，这尤其糟糕。准备反对此事的最好方法是建立与某些（小）延迟的连接。确定连接鲁棒性的重要因素是提前延迟了多远。我们给出了两个极端情况的多项式时间算法：出发前知道的延迟和延迟没有事先警告（后者导致了两人游戏场景）。有趣的是，在后一种情况下，我们表明，如果行程被要求是一条途径，则问题将成为PSPACE的完整。
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.
