A Note on Admissible Exchanges in Spanning Trees

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1974
Accession Number
ADA002922

Entities

People

  • Darwin Dee Klingman
  • Fred W. Glover

Organizations

  • University of Texas at Austin

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Colorado
  • Commerce
  • Computer Programming
  • Contracts
  • Graph Theory
  • Linear Programming
  • Military Research
  • Security
  • United States
  • United States Government
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Theoretical Analysis.