Finding a minimum source set in temporal graphs

Saksham Yadav

doi:10.1016/j.tcs.2025.115624

Finding a minimum source set in temporal graphs

2025-11-01

0

PRE

AI

DOI：10.1016/j.tcs.2025.115624

原文链接

原文求助

摘要

En 中文

时序图是指图拓扑结构及/或图的其它属性随时间变化的图。这类图是有效建模具有时变拓扑结构的网络（其中网络的边集和/或顶点集随时间变化）的工具。针对这类网络的不同图问题进行研究，对于为分布式系统中的基本问题（如信息传播、路由、广播等）提供高效解决方案至关重要。在本文中，我们基于时序图中顶点可达性的概念定义了源集。我们研究了在给定一个时序图的顶点集的情况下，构建该图的最小源集的问题。具体而言，对于给定的顶点集，我们构建一个源顶点集合的最小基数子集，使得给定集中的每个顶点至少从一个源集顶点可达。我们证明，即使当时序图是二分图且每个顶点的度数上限为某个正整数S（其中S的值小至3）时，该问题仍然是NP完全问题。我们证明，当每个顶点的入度上限为一个正整数（小至2），且每个顶点的出度上限为一个正整数（小至3）时，该问题对于有向二分静态图仍然是NP完全问题。然后，我们提出了一个时间复杂度为O(n)的算法，用于解决具有n个顶点且每个顶点的入度和出度均为2的有向二分静态图的最小源集问题。利用该解决方案，我们将方法扩展，为具有n个顶点、m条边、寿命为7且每个顶点恰好能到达2个其他顶点并被恰好2个其他顶点到达的受限类时序图，提出了一个时间复杂度为O(mn(log 7 + log n))的最小源集算法。最后，我们提出了一个线性时间算法，用于解决在根有时序树上的最小源集问题，其中所有叶子节点都是给定的顶点，需要为这些顶点找到最小源集。

Keyword:

Minimum source set

Source set

Temporal source set

Temporal graphs

Temporal tree

Dynamic graphs

Finding a minimum source set in temporal graphs

摘要

期刊

机构