Accession Number:

ADA002922

Title:

A Note on Admissible Exchanges in Spanning Trees

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:

9.0

Abstract:

A constructive result is given for identifying a complete pairing one-one matching of edges from two spanning trees such that each pair gives rise to an admissible exchange relative to the first tree. The result is considerable stronger than the standard result concerning the existance of admissible exchanges in spanning trees, and finds application in establishing the validity of swapping algorithms for problems in undirected graphs.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE