Accession Number:

ADA014424

Title:

The Dependence Graph for Bases in Matroids,

Descriptive Note:

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1975-05-01

Pagination or Media Count:

32.0

Abstract:

This paper discusses a certain graph, called the dependence graph the DPG, that can be defined naturally for a given independent set in a matroid. The author is mainly concerned with the DPG of bases, and the author studies what the DPG of a base tells about the matroid. It is shown that there is a nice connection between the DPG and duality, and between the DPG and connectivity for matroids. This last fact leads to an algorithm for determining the connected components of a matroid and also to one for computing a circuit containing two given distinct elements in the same such component. A simple algorithm using depth-first search is given for solving this last problem for graphic matroids.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE