Equivalence-free exhaustive generation of matroid representations

Warning

This publication doesn't include Institute of Computer Science. 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:	Institute for Theoretical Computer Science Highly Parallel and Distributed Computing Systems