Edge Exploration of Temporal Graphs
Edge Exploration of Temporal Graphs
复制标题
DOI：
10.1007/s00453-022-01018-7
复制
发表时间：
2021-03
期刊：
影响因子：
1.1
通讯作者：
B. Bumpus;Kitty Meeks
中科院分区：
文献类型：
--
作者：
B. Bumpus;Kitty Meeks
我们介绍了一个自然的时间模拟欧拉电路和证明，在静态的情况下，它是很难确定是否一个给定的时间图是时间欧拉，即使强限制被放置在底层图形的结构和每个边缘是活跃的只有三次。然而，我们确实得到了一个算法，一个新的参数称为interval-membership-widthwhich限制了分配给不同边缘的时间，我们相信，这个参数将是独立的兴趣为其他时间图问题。我们的技术还使我们能够解决Akrida，Mertzios和Spirakis [CIAC 2019]关于探索时间恒星的相关问题的两个开放问题。
We introduce a natural temporal analogue of Eulerian circuits and prove that, in contrast to the static case, it is-hard to determine whether a given temporal graph is temporally Eulerian even if strong restrictions are placed on the structure of the underlying graph and each edge is active at only three times. However, we do obtain an-algorithm with respect to a new parameter calledinterval-membership-widthwhich restricts the times assigned to different edges; we believe that this parameter will be of independent interest for other temporal graph problems. Our techniques also allow us to resolve two open questions of Akrida, Mertzios and Spirakis [CIAC 2019] concerning a related problem of exploring temporal stars.