Source Sets in Temporal Graphs
摘要
Temporal graphs are introduced 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 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 have proved that this problem is NP-complete. We have developed a novel \(O(n^2)\) 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 \mathcal {T} + \log n))+ n^2)\) time algorithm for the minimum source set problem in a restricted class of temporal graphs with n vertices, m edges, lifetime \(\mathcal {T}\) such that each vertex can reach exactly 2 other vertices and can be reached from exactly 2 other vertices.