Finding Minimum Spanning Trees with a Fixed Number of Links at a Node
TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES
Pagination or Media Count:
The paper addresses a variant of the minimum spanning tree problem in which a given node is required to have a fixed number of incident edges. It is shown that this problem, which is combinatorially a level of complexity beyond the ordinary minimum spanning tree problem, can be solved by a highly efficient quasi-greedy algorithm. Applications include a telecommunication linking problem and a new relaxation strategy for the traveling salesman problem via appropriately defined order-constrained one-trees.
- Operations Research