Equivalence-free exhaustive generation of matroid representations
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | Discrete Applied Mathematics |
| MU Faculty or unit | |
| Citation | |
| Web | http://dx.doi.org/10.1016/j.dam.2005.12.001 |
| Field | Informatics |
| Keywords | Matroid representation; Matroid extension; Exhaustive generation; Canonical construction path |
| Description | In this paper we present an algorithm for the problem of exhaustive equivalence-free generation of 3-connected matroids which are represented by a matrix over some finite (partial) field, and which contain a given minor. The nature of this problem is exponential, and it appears to be much harder than, say, isomorph-free generation of graphs. Still, our algorithm is very suitable for practical use, and it has been successfully implemented in our matroid computing package MACEK [http://www.mcs.vuw.ac.nz/research/macek, 2001-05]. |
| Related projects: |