Reports
A Good Algorithm for Minimum Spanning Trees with a Degree Constraint ; CU-CS-105-77 Public Deposited
https://scholar.colorado.edu/concern/reports/kp78gh298
- Abstract
- 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.
- Creator
- Date Issued
- 1977-06-01
- Academic Affiliation
- Last Modified
- 2019-12-21
- Resource Type
- Rights Statement
- Language
Relationships
Items
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
aGoodAlgorithmForMinimumSpanningTreesWithADegreeConstra.pdf | 2019-12-21 | Public | Download |