.png){kind=icon}
.png){kind=icon}
Return
Finding a minimum source set in temporal graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.tcs.2025.115624.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Temporal graphs are graphs where the graph topology and/or other properties of the graph changes with time. These types of graphs are efficient tool to model different networks with time-dependent topologies where edge and/or vertex sets of the network change with time. Addressing different graph problems on these types of networks are important to provide efficient solutions to fundamental problems in distributed systems such as information spreading, routing, broadcasting, etc. In this paper, we define source sets based on the concept of reachability of vertices in a temporal graph. We address the problem of constructing minimum source sets for a given set of vertices in a temporal graph. In particular, for a given set of vertices, we construct a minimum cardinality subset of source vertices such that each vertex in the given set is reachable from at least one vertex in the source set. We prove that this problem is NP-complete even when the temporal graph is bipartite and the degree of each vertex is upper bounded by some positive integer S where the value of S is as small as 3. We prove that this problem is NP-complete for directed bipartite static graphs when in-degree of each vertex is upper bounded by a positive integer as small as 2, and out-degree of each vertex is upper bounded by a positive integer as small as 3. Then, we propose a O(n) time algorithm to address minimum source set problem for static directed bipartite graphs with n vertices and each vertex with fixed in-degree 2 and out-degree 2. Leveraging this solution, we extended our approach to develop a O(mn(log 7 + log n)) time algorithm for the minimum source set problem in a restricted class of temporal graphs with n vertices, m edges, lifetime 7 such that each vertex can reach exactly 2 other vertices and can be reached from exactly 2 other vertices. Finally, we propose a linear time algorithm to address the problem on a rooted temporal tree where all the leaves are the given vertices for which we need to find a minimum source set.
Keywords:
Minimum source set
Source set
Temporal source set
Temporal graphs
Temporal tree
Dynamic graphs
Journal
IF:
1
Papers:
248
Citations:
1.0W
Organization
View more organizations