Premium
A good algorithm for smallest spanning trees with a degree constraint
Author(s) -
Gabow H. N.
Publication year - 1978
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230080304
Subject(s) - spanning tree , minimum spanning tree , combinatorics , degree (music) , mathematics , vertex (graph theory) , graph , minimum degree spanning tree , vertex connectivity , kruskal's algorithm , enhanced data rates for gsm evolution , discrete mathematics , computer science , telecommunications , physics , acoustics
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.