A good algorithm for smallest spanning trees with a degree constraint | Zendy

Gabow H. N. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research