A matroid generalization of a result on row-Latin rectangles (Q1818212)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A matroid generalization of a result on row-Latin rectangles |
scientific article |
Statements
A matroid generalization of a result on row-Latin rectangles (English)
0 references
22 March 2000
0 references
The paper is devoted to some generalization of an \textit{A. A. Drisko} result [J. Comb. Theory, Ser. A 84, No. 2, 181-195 (1998; Zbl 0915.05025)] on finding such a minimum value of \(m\) that every \(m \times n\) row-Latin rectangle has a transversal. Due to a suggested new proof of an A. A. Drisko result, the author decreases the time complexity of the computational algorithm for finding a transversal from \(O(n^4)\) to \(O(n^2)\). The paper contains also a set of unsolved problems which are suggested for further investigations and references properly covering the history of finding transversals in row-Latin rectangles.
0 references
Latin squares
0 references
Latin rectangles
0 references
transversals
0 references