The Dependence Graph for Bases in Matroids,
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1975
- Accession Number
- ADA014424
Entities
People
- Stein Krogdahl
Organizations
- Stanford University