Considerable effort has been devoted to establishing concepts and designing algorithms that are useful for graph data management. While most work so far has focused on static graphs, there are many networks with time information, i.e.,  temporal graphs , such as social network messages, phone calls, public transportation, and neural networks. Even the most fundamental problems for static graphs become non-trivial for temporal graphs. In this paper, we explore the  minimum-weight spanning tree problem  on temporal graphs, which was recently proposed by Huang  et al . [SIGMOD 2015]. Even though this problem is proven to be NP-hard, we design practically efficient  exact  algorithms using  integer programming . Experimental results confirm that the proposed algorithms can produce better solutions than a previously proposed approximation algorithm.
['Takuto Ikuta', 'Takuya Akiba']
Integer programming approach for directed minimum spanning tree problem on temporal graphs