COMPLEMENTARY SPANNING TREES

Abstract

Given a network G whose arcs partition into non-overlapping 'clubs' (sets) R sub i, D. Ray Fulkerson has considered the problem of constructing a spanning tree such that no two of its arcs belong to (represent) the same club and has stated necessary and sufficient conditions for such trees to exist. When each club R sub i consists of exactly two arcs, we shall refer to each of the arc pair as the 'complement' of the other, and the representative tree as a complementary tree. Our objective is to prove the following theorem: If there exists one complementary tree, there exists at least two.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1969
Accession Number
AD0702898

Entities

People

  • George Bernard Dantzig

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computer Science
  • Computers
  • Contracts
  • Convex Sets
  • Heuristic Methods
  • Linear Programming
  • Matrix Games
  • Military Research
  • Nuclear Energy
  • Quadratic Programming
  • Sequences
  • Simplex Method
  • Theorems
  • United States

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • STEM Education