论文标题
时间匹配的更快的参数化算法
A Faster Parameterized Algorithm for Temporal Matching
论文作者
论文摘要
时间图是在同一顶点集上的一系列图（称为层） - 描述图形拓扑，该图会随着时间的流逝而受离散变化。 A $Δ$-temporal matching $M$ is a set of time edges $(e,t)$ (an edge $e$ paired up with a point in time $t$) such that for all distinct time edges $(e,t),(e',t') \in M$ we have that $e$ and $e'$ do not share an endpoint, or the time-labels $t$ and $t'$ are at least $Δ$ time units apart. Mertzios等。 [stacs '20]提供了$ 2^{o（δν）} \ cdot | {\ Mathcal g} |^{o（1）} $ - 时间算法，以计算$Δ$Δ$ - temporamal的最大大小，以$Δ$ -TMAILEAL匹配的时间图$ \ Mathcal G $ \ Mathcal G $，其中$ \ $ | $ | $ | $ | $ | $ | $ | $ | $ c | $ | $δ$ -VERTEX $ \ MATHCAL G $。 $δ$ -VERTEX封面编号是最小数字$ν$，因此，临时图的任何$δ$连续层的结合的经典顶点封面数是$ν$的上限。我们展示了一种改进的算法，以计算最大尺寸的$δ$ -Tmporal匹配，运行时间为$δ^{o（ν）\ cdot | \ Mathcal g | $，因此以$δ$为准。
A temporal graph is a sequence of graphs (called layers) over the same vertex set -- describing a graph topology which is subject to discrete changes over time. A $Δ$-temporal matching $M$ is a set of time edges $(e,t)$ (an edge $e$ paired up with a point in time $t$) such that for all distinct time edges $(e,t),(e',t') \in M$ we have that $e$ and $e'$ do not share an endpoint, or the time-labels $t$ and $t'$ are at least $Δ$ time units apart. Mertzios et al. [STACS '20] provided a $2^{O(Δν)}\cdot |{\mathcal G}|^{O(1)}$-time algorithm to compute the maximum size of a $Δ$-temporal matching in a temporal graph $\mathcal G$, where $|\mathcal G|$ denotes the size of $\mathcal G$, and $ν$ is the $Δ$-vertex cover number of $\mathcal G$. The $Δ$-vertex cover number is the minimum number $ν$ such that the classical vertex cover number of the union of any $Δ$ consecutive layers of the temporal graph is upper-bounded by $ν$. We show an improved algorithm to compute a $Δ$-temporal matching of maximum size with a running time of $Δ^{O(ν)}\cdot |\mathcal G|$ and hence provide an exponential speedup in terms of $Δ$.
