Equivalence-free exhaustive generation of matroid representations

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr

Year of publication 2006
Type Article in Periodical
Magazine / Source Discrete Applied Mathematics
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.