We address a problem of maintaining a minimum spanning tree (MST) in a network, in which dynamic changes occur, such as insertions of new edges and deletions of existing edges. There are some previous works focusing on static network that does not take into account dynamic changes.
In this paper, we propose distributed algorithms that find a MST in dynamic network. For each change, our algorithms inform nodes of the change using the properties of tree and nodes that relate to change cooperate in finding a minimum spanning tree.
Given a weighted graph G with N nodes and E edges, our algorithm has message complexity with min{O(κD)+O(N), O(N log N+E)} in insertion of κ edges and O(N log κ+E) in deletion of κ edges, where D is a diameter of resulting spanning tree. Also we show the lower bound for these problems.
