×

Equivalence-free exhaustive generation of matroid representations. (English) Zbl 1090.05012

Summary: 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].

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices

Software:

MACEK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] C.R. Coullard, Minors of 3-connected matroids and adjoints of binary matroids, Ph.D. Thesis, Northwestern University, 1985.; C.R. Coullard, Minors of 3-connected matroids and adjoints of binary matroids, Ph.D. Thesis, Northwestern University, 1985.
[2] J.S. Dharmatilake, Binary matroids of branch-width 3, Ph.D. Dissertation, Ohio State University, 1994.; J.S. Dharmatilake, Binary matroids of branch-width 3, Ph.D. Dissertation, Ohio State University, 1994.
[3] P. Hliněný, The M \(\textsc{ACEK} \langle;\rangle;\); P. Hliněný, The M \(\textsc{ACEK} \langle;\rangle;\)
[4] Hliněný, P., On the excluded minors for matroids of branch-width three, Electron. J. Combin., 9, #R32 (2002) · Zbl 1003.05029
[5] Hliněný, P., Using a computer in matroid theory research, Acta Math. Univ. M. Belii, 11, 27-44 (2004) · Zbl 1063.05030
[6] P. Hliněný, Combinatorial generation of matroid representations: theory and practice, Proceedings AACC 2005, Kathmandu, Nepal. Advances in Computer Science and Engineering, Imperial College Press, 2006; to appear.; P. Hliněný, Combinatorial generation of matroid representations: theory and practice, Proceedings AACC 2005, Kathmandu, Nepal. Advances in Computer Science and Engineering, Imperial College Press, 2006; to appear.
[7] Kingan, R. J.; Kingan, S. R.; Myrvold, W., On matroid generation, Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Congr. Numer., 164, 95-109 (2003) · Zbl 1051.05024
[8] McKay, B. D., Isomorph-free exhaustive generation, J. Algorithms, 26, 306-324 (1998) · Zbl 0894.68107
[9] Oxley, J. G., Matroid Theory (1992), Oxford University Press: Oxford University Press Oxford · Zbl 0784.05002
[10] R. Pendavingh, personal communication, 2004.; R. Pendavingh, personal communication, 2004.
[11] C. Semple, G.P. Whittle, On representable matroids having neither \(U_{2 , 5} U_{3 , 5}\); C. Semple, G.P. Whittle, On representable matroids having neither \(U_{2 , 5} U_{3 , 5}\) · Zbl 0865.05027
[12] Semple, C.; Whittle, G. P., Partial fields and matroid representation, Adv. Appl. Math., 17, 184-208 (1996) · Zbl 0859.05035
[13] Seymour, P. D., Decomposition of regular matroids, J. Combin. Theory Ser. B, 28, 305-359 (1980) · Zbl 0443.05027
[14] Tutte, W. T., A homotopy theorem for matroids, Trans. Amer. Math. Soc., 88, 144-174 (1958) · Zbl 0081.17301
[15] Tutte, W. T., Connectivity in matroids, Cand. J. Math., 18, 1301-1324 (1966) · Zbl 0149.21501
[16] X. Zhou, Some excluded minor theorems for binary matroids, Ph.D. Thesis, The Ohio State University, 2003.; X. Zhou, Some excluded minor theorems for binary matroids, Ph.D. Thesis, The Ohio State University, 2003.
[17] Zhou, X., On internally 4-connected non-regular binary matroids, J. Combin. Theory Ser. B, 91, 327-343 (2004) · Zbl 1051.05027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.