论文标题
时间图
Edge-Disjoint Branchings in Temporal Graphs
论文作者
论文摘要
A temporal digraph ${\cal G}$ is a triple $(G, γ, λ)$ where $G$ is a digraph, $γ$ is a function on $V(G)$ that tells us the timestamps when a vertex is active, and $λ$ is a function on $E(G)$ that tells for each $uv \in E(G)$ when $u$ and $v$ are linked.给定静态的Digraph $ g $和子集$ r \ subseteq v（g）$，带有root $ r $的分支是$ g $的子数字，它的子数字恰好有一个路径，从$ r $到每个$ v \ in v（g）$。在本文中，我们考虑了埃德蒙兹（Edmonds）的经典结果的时间版本，即查找$ k $ edge-edisexchaint跨度分支的问题分别扎根于给定的$ r_1，\ cdots，r_k $。我们介绍并研究了跨越分支的不同定义，以及在时间图的上下文中的边缘 - 偶相关。如果根部可以在某些时候$ v $处于活动状态的某个时候，则分支$ {\ cal b} $如果root可以在某些时候到达$ g $的每个顶点$ v $，而如果$ v $在$ v $处于活动状态的情况下，则是暂时的。另一方面，两个分支$ {\ cal b} _1 $和$ {\ cal b} _2 $，如果他们不使用$ g $的相同边缘，则是边缘 - 偶，如果他们可以使用$ g $的相同边缘，但在不同的时间，它们是临时边缘 - 偶。这使我们对分支机构的分离进行了四个定义，我们证明，与静态情况不同，其中只能在多项式时间内计算其中一个，即，在非常严格的假设下，即使是$ \ mathsf {np} $ - 完整的，其他版本是$ \ mathsf {np} $完整的，而其他版本则是$ \ mathsf {np} $ - 完整的假设。
A temporal digraph ${\cal G}$ is a triple $(G, γ, λ)$ where $G$ is a digraph, $γ$ is a function on $V(G)$ that tells us the timestamps when a vertex is active, and $λ$ is a function on $E(G)$ that tells for each $uv \in E(G)$ when $u$ and $v$ are linked. Given a static digraph $G$, and a subset $R\subseteq V(G)$, a spanning branching with root $R$ is a subdigraph of $G$ that has exactly one path from $R$ to each $v\in V(G)$. In this paper, we consider the temporal version of Edmonds' classical result about the problem of finding $k$ edge-disjoint spanning branchings respectively rooted at given $R_1,\cdots,R_k$. We introduce and investigate different definitions of spanning branchings, and of edge-disjointness in the context of temporal graphs. A branching ${\cal B}$ is vertex-spanning if the root is able to reach each vertex $v$ of $G$ at some time where $v$ is active, while it is temporal-spanning if $v$ can be reached from the root at every time where $v$ is active. On the other hand, two branchings ${\cal B}_1$ and ${\cal B}_2$ are edge-disjoint if they do not use the same edge of $G$, and are temporal-edge-disjoint if they can use the same edge of $G$ but at different times. This lead us to four definitions of disjoint spanning branchings and we prove that, unlike the static case, only one of these can be computed in polynomial time, namely the temporal-edge-disjoint temporal-spanning branchings problem, while the other versions are $\mathsf{NP}$-complete, even under very strict assumptions.
