P-time event graphs (P-TEGs) are specific timed discrete-event systems, in which the timing of events is constrained by intervals. An important problem is to check, for all natural numbers $d$, the existence of consistent $d$-periodic trajectories for a given P-TEG. Let us consider a different, seemingly unrelated problem in graph theory: given three arbitrary square matrices $P$, $I$ and $C$ with elements in $\mathbb{R}\cup\{-\infty\}$, find all real values of parameter $\lambda$ such that the parametric directed graph having arcs weights of the form $w((j,i)) = \max(P_{ij} + \lambda, I_{ij} - \lambda, C_{ij})$ (for all arcs $(j,i)$) does not contain circuits with positive weight. In a related paper, we have proposed a strongly polynomial algorithm that solves the latter problem faster than other algorithms reported in literature. In the present paper, we show that the first problem can be formulated as an instance of the second; consequently, we prove that the same algorithm can be used to find $d$-periodic trajectories in P-TEGs faster than with previous approaches.
翻译:P- 时间事件图表( P- TEGs) 是特定的时间分解事件系统, 其中事件的时间间隔受时间间隔限制。 一个重要问题是对所有自然数字的美元进行检查。 对于给定的 P- TEG 来说, 是否有一致的美元周期轨迹。 让我们在图形理论中考虑一个不同、 似乎无关的问题: 给三个任意的平方基 $P$, $I$和$C$, 其中含有$\mathbb{R ⁇ cup ⁇ _\\\infty ⁇ $元素, 找到所有参数 $\ lambda$ 的真实值。 重要的问题是, 使参数 $( j, i) 的参数方向图显示有 $w( j, i) =\ max( P ⁇ j) +\ lambda, I ⁇ j} +\ lambda, Cíj} $( 对于所有 rcs $ (j, i) $) 都不包含正重的电路路。 在相关文件中, 我们提议了一个强烈的多式算算算算算方法, 第一次解决后一个问题, 我们在文献中可以证明过去使用的运算法中, 。