|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 5 of 9 found articles
| Title: |
Full transversal matroids, strict gammoids, and the matroid components problem |
| Author: |
Mummy, Mark Stephen |
| Appeared in: |
Linear & multilinear algebra |
| Paging: | Volume 19 (1986) nr. 2 pages 97-116 |
| Year: |
1986-04 |
| Contents: |
We provide two algorithms for finding dependence graphs both in a full transversal matroid and in its dual, a strict gammoid. The first algorithm is based on directed paths in the directed graph associated with a strict gammoid; its complexity is O(|L|(|V-L|+|E|)), where L is the link-set of the gammoid. The second algorithm is based on a special property of Gaussian elimination in a matrix of indeterminates representing a full transversal matroid; it complexity is o(m2n), where m is the rank of the matroid and n the cardinality of the underlying set. We provide an algorithm for listing all bases in, and calculating the Whitney and Tutte polynomials for, a full transversal matroid or a strict gammoid. The complexity of this algorithm is 0(N(n-m) (|E| + m2)), where N is the number of bases. |
| Publisher: |
Taylor & Francis |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 5 of 9 found articles
| << previous | next >> |