Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings
Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings
复制标题
组合算法 - 第 33 届国际研讨会，IWOCA 2022，德国特里尔，2022 年 6 月 7-9 日，会议记录
DOI：
10.1007/978-3-031-06678-8_16
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Bocci C
中科院分区：
文献类型：
--
作者：
Bocci C
NP完全图问题集群编辑试图通过对边进行尽可能少的编辑来将静态图转换为不相交的团的联合。我们引入一个自然的解释这个问题的时间图，其边集随时间变化。这个问题是NP完全的，即使限制到时间图的基础图是一个路径，但我们得到两个多项式时间算法的限制情况下。在静态设置中，这是众所周知的，一个图是一个不相交的联盟的集团当且仅当它不包含诱导副本的P 3，我们证明，没有一般的表征，涉及最多四个顶点的集可以存在于时间设置，但获得一个完整的表征，涉及禁止配置在最多五个顶点。这种特性产生了一个FPT算法参数化的同时允许的修改次数和寿命的时间图。
The NP-complete graph problem Cluster Editing seeks to transform a static graph into a disjoint union of cliques by making the fewest possible edits to the edges. We introduce a natural interpretation of this problem in temporal graphs, whose edge sets change over time. This problem is NP-complete even when restricted to temporal graphs whose underlying graph is a path, but we obtain two polynomial-time algorithms for restricted cases. In the static setting, it is well-known that a graph is a disjoint union of cliques if and only if it contains no induced copy of P 3; we demonstrate that no general characterisation involving sets of at most four vertices can exist in the temporal setting, but obtain a complete characterisation involving forbidden configurations on at most five vertices. This characterisation gives rise to an FPT algorithm parameterised simultaneously by the permitted number of modifications and the lifetime of the temporal graph.