论文标题
Mengerian图：表征和识别
Mengerian graphs: characterization and recognition
论文作者
论文摘要
时间图$ {\ cal g} $是随时间变化的图。更具体地说，这是一对$（g，λ）$，其中$ g $是一个图，而$λ$是$ g $的边缘的一个函数，该函数描述了何时e（g）$中的每个边缘$ e \ extive。给定的顶点$ s，t \在v（g）$中，临时$ s，t $ path是$ g $中的一条路径，它在不缩减时间内穿越边缘；如果$ s，t $是不可变的，那么临时$ s，t $ cut是子集$ s \ subseteq v（g）\ setminus \ {s，t \} $，其删除的所有临时$ s，t $ paths。 众所周知，Menger的定理在这种情况下不满意，即，内部顶点脱节时间$ s的最大数量不一定等于临时$ s，t $ cut的最小尺寸。在开创性的论文中，如果平等在$（g，λ）$上符合每个功能$λ$，则Kempe，Kleinberg和Kumar（Stoc'2000）将图$ G $定义为Mengerian。然后，他们证明，如果允许每个边缘在$（g，λ）$中仅活跃一次，则$ g $是孟加利人，并且只有$ g $没有宝石作为拓扑辅助。在本文中，我们通过允许边缘不止一次活动来概括它们的结果，从而在禁止结构方面给出了表征。我们还提供多项式时间识别算法。
A temporal graph ${\cal G}$ is a graph that changes with time. More specifically, it is a pair $(G, λ)$ where $G$ is a graph and $λ$ is a function on the edges of $G$ that describes when each edge $e\in E(G)$ is active. Given vertices $s,t\in V(G)$, a temporal $s,t$-path is a path in $G$ that traverses edges in non-decreasing time; and if $s,t$ are non-adjacent, then a temporal $s,t$-cut is a subset $S\subseteq V(G)\setminus\{s,t\}$ whose removal destroys all temporal $s,t$-paths. It is known that Menger's Theorem does not hold on this context, i.e., that the maximum number of internally vertex disjoint temporal $s,t$-paths is not necessarily equal to the minimum size of a temporal $s,t$-cut. In a seminal paper, Kempe, Kleinberg and Kumar (STOC'2000) defined a graph $G$ to be Mengerian if equality holds on $(G,λ)$ for every function $λ$. They then proved that, if each edge is allowed to be active only once in $(G,λ)$, then $G$ is Mengerian if and only if $G$ has no gem as topological minor. In this paper, we generalize their result by allowing edges to be active more than once, giving a characterization also in terms of forbidden structures. We additionally provide a polynomial time recognition algorithm.
