Accession Number:

AD0779141

Title:

Finding Minimum Spanning Trees with a Fixed Number of Links at a Node

Descriptive Note:

Research rept.

Corporate Author:

TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES

Personal Author(s):

Report Date:

1974-04-01

Pagination or Media Count:

20.0

Abstract:

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE