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

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.

Open PDF

Document Details

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

Entities

People

  • Darwin Dee Klingman
  • Fred W. Glover

Organizations

  • University of Texas at Austin

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Colorado
  • Commerce
  • Computations
  • Computer Programming
  • Computers
  • Flow Network
  • Graph Theory
  • Graphs
  • Linear Programming
  • Mathematics
  • Military Research
  • United States
  • United States Government
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research