ON BOUNDS FOR COMPLEMENTARY TREES IN A GRAPH

Abstract

It was shown elsewhere by Dantzig that if there exits one complementary tree in the undirected network G(G epsilon eta(n)) then there exists at least two. The proof there is by means of an algorithm which finds a different complementary tree from a given one. It is shown in this paper that using an extended form of Dantzig's algorithm can lead to a stronger result: if there exists one complementary tree in G(G epsilon eta(n)) then there exists at least four. Also some examples are provided to establish an upper bound on the smallest number of complementary trees in a network G(G epsilon eta(n)) which has at least one complementary tree.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1969
Accession Number
AD0701309

Entities

People

  • Ilan Adler

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Computer Science
  • Contracts
  • Military Research
  • Operations Research
  • Security
  • Sequences
  • Simplex Method
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.