An Algorithm for kth Minimum Spanning Tree

Minimum Spanning Tree problem is a well-known problem in graph theory. There are many polynomial time algorithms, for finding minimum spanning tree of an undirected connected graph. The kthkth minimum spanning tree problem is a variation of minimum spanning tree problem that finds kthkth minimum spanning tree of an undirected connected graph, for some integer k. An algorithm of time complexity O(k|E‖V|logk)O(k|E‖V|logk) and space complexity O(k.|V|+|E|)O(k.|V|+|E|) for finding kthkth minimum spanning tree is proposed in this paper. This algorithm is used to solve degree constrained minimum spanning tree problem, an NP-complete problem, with exponential time complexity.