| Title: | COMBINATORIAL GENERATION OF MATROID REPRESENTATIONS: THEORY AND PRACTICE |
| DOI No: | 10.1142/9781860948534_0001 |
| Source: | INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD (pp 3-7)
|
| Author(s): | PETR HLINĚNÝ
Supported by the Institute of Theoretical Computer Science ITI, project no. 1M0545.
Faculty of Informatics, Masaryk University in Brno, Botanická 68a, 602 00 Brno, Czech Rep.
|
| Abstract: | Matroids (also called combinatorial geometries) present a strong combinatorial generalization of graphs and matrices. Unlike isomorph-free generation of graphs, which has been extensively studied both from theoretical and practical points of view, not much research has been done so far about matroid generation. Perhaps the main problem with matroid generation lies in a very complex internal structure of a matroid. That is why we focus on generation of suitable matroid representations, and we outline a way how to exhaustively generate matroid representations over finite fields in reasonable computing time. In particular, we extend here some enumeration results on binary (over the binary field) combinatorial geometries by Kingan et al. We use the matroid generation algorithm of [P. Hliněný, Equivalence-Free Exhaustive Generation of Matroid Representations] and its implementation in MACEK; see http://www.cs.vsb.cz/hlineny/MACEK. |
| Full Text: | View full text in PDF format (268KB) |
| TOC: | Back to Table of Contents |
|
|
