×

zbMATH — the first resource for mathematics

A catalog of minimally nonideal matrices. (English) Zbl 0928.15011
This paper describes a backtracking algorithm for the enumeration of nonisomorphic minimally nonideal \(n\times n\)-matrices that are not degenerate projective planes. The application of this algorithm for \(n\leq 12\) yielding 20 such matrices, adding 5 matrices to the previously known. For greater dimensions, \(n=14\) and \(n=17\), 13 new matrices are given. For nonsquare matrices, 38 new minimally nonideal matrices are described.
Reviewer: G.Bonanno (Davis)

MSC:
15B36 Matrices of integers
Software:
cdd
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cornuejols G, Novick B (1994) Ideal 0, 1 matrices. J. Comb. Theory Ser. B 60:145-157 · Zbl 0794.05077 · doi:10.1006/jctb.1994.1009
[2] Ding G (1993) Clutters with ?2 = 2 \(\cdot\) ?. Discr. Math. 115:141-152 · Zbl 0771.05003
[3] Fukuda K ?cdd.c?: A C code for enumerating vertices and extreme rays. Available by anonymous ftp from iforl3.ethz.ch, directory pub/fukuda/cdd.
[4] Fukuda K (1995) Private communication.
[5] Fukuda K, Matsui T (1994) Finding all the perfect matchings in bipartite graphs. Appl. Math. Lett. 7:15-18 · Zbl 0792.68129 · doi:10.1016/0893-9659(94)90045-0
[6] Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness. Freeman · Zbl 0411.68039
[7] Johnson DS (1982) The NP-completness column, an ongoing guide. J. Algorithms 3:288-300 · Zbl 0494.68050 · doi:10.1016/0196-6774(82)90026-8
[8] Lehman A (1979) On the width-length inequality. Mimeographic notes (1965), Math. Progr. 17: 403-417 · Zbl 0418.90040 · doi:10.1007/BF01588263
[9] Lehman A (1990) On the width-length inequality and degenerate projective planes. In: Cook W, Seymour PD (eds.) Polyhedral Combinatorics. DIMACS series in Discrete Mathematics and Computer Science, vol. 1, Amer. Math. Soc., pp. 101-105 · Zbl 0747.05063
[10] Luks EM (1980) Isomorphism of bounded valence can be tested in polynomial time. Proc. FOCS 21:42-49
[11] McKay BD (1996) Isomorphism-free exhaustive generation. Research report, Australian National University, Canberra
[12] Nemhauser G, Wolsey L (1988) Integer and combinatorial optimization. Wiley · Zbl 0652.90067
[13] Novick B (1990) Ideal 0,1 matrices. Ph.D. dissertation, Carnegie Mellon University, Pittsburgh, PA
[14] Padberg MW (1993) Lehman’s forbidden minor characterization of ideal 0-1 matrices. Discr. Math. 111:409-420 · Zbl 0798.05010 · doi:10.1016/0012-365X(93)90178-V
[15] Qi L (1989) On the set covering polytope and the MFMC-clutter. School of Mathematics, University of South Wales
[16] Read RC (1981) A survey of graph generation techniques. In: Combinatorial Mathematics VIII, Lecture Notes in Mathematics 884, Springer, pp. 77-89
[17] Seymour PD (1977) The matroids with the max-flow min-cut property. J. Comb. Theory Ser. B 23:189-222 · Zbl 0375.05022 · doi:10.1016/0095-8956(77)90031-4
[18] Seymour PD (1990) On Lehman’s width-length characterization. In: Cook W, Seymour PD (eds.) Polyhedral Combinatorics. DIMACS series in Discrete Mathematics and Computer Science, vol. 1, Amer. Math. Soc., pp. 107-117 · Zbl 0747.05066
[19] Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM J. Comput. 8:410-421 · Zbl 0419.68082 · doi:10.1137/0208032
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.