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
    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
    0 references
    Latin squares
    0 references
    Latin rectangles
    0 references
    transversals
    0 references
    0 references
    0 references