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) $) 都不包含正重的电路路。 在相关文件中, 我们提议了一个强烈的多式算算算算算方法, 第一次解决后一个问题, 我们在文献中可以证明过去使用的运算法中, 。

0
下载
关闭预览

相关内容

专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
84+阅读 · 2020年12月5日
专知会员服务
123+阅读 · 2020年9月8日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
异常检测论文大列表:方法、应用、综述
专知
126+阅读 · 2019年7月15日
已删除
将门创投
5+阅读 · 2019年4月29日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年4月21日
VIP会员
相关VIP内容
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
84+阅读 · 2020年12月5日
专知会员服务
123+阅读 · 2020年9月8日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
异常检测论文大列表:方法、应用、综述
专知
126+阅读 · 2019年7月15日
已删除
将门创投
5+阅读 · 2019年4月29日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员