Abstract:We introduce the Temporally Edge Disjoint Schedule Completion (TEDSC) problem in which we need to cover a set of temporal edge demands $D$ by routing $k$ temporal walks through a directed static graph while remaining temporally edge disjoint. This problem combines the temporal aspects of train routing and passenger demands with the static nature of real-world rail networks. We show how to solve TEDSC in polynomial time. Motivated by real-world constraints, we next investigate two restricted variants of TEDSC in which each walk can travel only for some bounded distance or time $h$. For both variants, we present a $(2-h^{-1})$-approximation algorithm and fully characterize the parameterized landscape with respect to $k$, $h$, and $|D|$. Surprisingly, if we restrict the underlying train network, the two variants diverge: The distance variant stays $W[1]$-hard parameterized by $k$ even on a path of three vertices, whereas the time variant admits a polynomial-time algorithm on every fixed bidirected star graph.
From: Niklas Mohrin [view email]
[v1]
Thu, 30 Apr 2026 11:45:04 UTC (631 KB)
[v2]
Wed, 6 May 2026 12:50:34 UTC (631 KB)
[v3]
Tue, 4 Aug 2026 14:05:32 UTC (667 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。