The generalized column incidence graph and a matroid base-listing algorithm |
| |
Authors: | Mark Stephen Mummy |
| |
Institution: |
a Department of Mathematics, University College of San Diego, La Jolla, California |
| |
Abstract: | The generalized column incidence graph of a matroid base is defined, and it is shown that all elements on a minimal path in this graph lie in a common circuit. Also, an algorithm is provided which lists all bases of a matroid and calculates the Whitney and Tutte polynomials. The complexity of this algorithm is shown to be O(mN(n- m)(c(M) + m)), where Mis a matroid of rank mon a set of cardinality nNis the number of bases of M, and c(M) is the complexity of checking independence in M. |
| |
Keywords: | |
本文献已被 InformaWorld 等数据库收录! |
|