Given a connected graph with edge costs, we seek a spanning tree having a specified degree at one vertex r, with cost as small as possible. A previous algorithm, using edge exchanges, has run time 0(V^2); we improve this to 0(E log log V+V log V). Here V and E are the number of vertices and edges. The algorithm uses edge exchanges ordered efficiently on a reduced graph; it also uses efficient algorithms for minimum spanning trees and priority queues.
展开▼
机译：给定一个带有边成本的连通图，我们寻求在一个顶点r上具有指定度的生成树，并且其成本应尽可能小。使用边缘交换的先前算法的运行时间为0（V ^ 2）；我们将其提高到0（E log log V + V log V）。这里V和E是顶点和边的数量。该算法使用在简化图上有序排列的边缘交换。它还使用有效的算法来最小化生成树和优先级队列。
展开▼
