|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 5 van 9 gevonden artikelen
| Titel: |
Full transversal matroids, strict gammoids, and the matroid components problem |
| Auteur: |
Mummy, Mark Stephen |
| Verschenen in: |
Linear & multilinear algebra |
| Paginering: | Jaargang 19 (1986) nr. 2 pagina's 97-116 |
| Jaar: |
1986-04 |
| Inhoud: |
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. |
| Uitgever: |
Taylor & Francis |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 5 van 9 gevonden artikelen
| << vorige | volgende >> |