Minimum Spanning Trees in Temporal Graphs

The computation of Minimum Spanning Trees (MSTs) is a fundamental graph problem with important applications. However, there has been little study of MSTs for temporal graphs, which is becoming common as time information is collected for many existing networks. We define two types of MSTs for temporal graphs, MST a and MST w, based on the optimization of time and cost, respectively. We propose efficient linear time algorithms for computing MST a. We show that computing MST w is much harder. We design efficient approximation algorithms based on a transformation to the Directed Steiner Tree problem (DST). Our solution also solves the classical DST problem with a better time complexity and the same approximation factor compared to the state-of-the-art algorithm. Our experiments on real temporal networks further verify the effectiveness of our algorithms. For MST w, our solution is capable of shortening the runtime from 10 hours to 3 seconds.