Abstract
Given a graph G = (V, E) with a weight function w on its edges and a positive integer number K, the Kth best spanning tree (KBST) problem is to find K distinct spanning trees T-1, T-2,..., T-K such that there is no spanning tree with a weight less ( respectively more) than their weights. This problem is NP-hard. We improve the running time complexity of KBST in series parallel graphs. KBST has applications in computer network routing optimization.