A general approach to avoiding two by two submatrices

V.G. Deineko, R. Rudolf, G.J. Woeginger

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    4 Citaten (Scopus)

    Samenvatting

    A matrixC is said to avoid a set of matrices, if no matrix of can be obtained by deleting some rows and columns ofC. In this paper we consider the decision problem whether the rows and columns of a given matrixC can be permuted in such a way that the permuted matrix avoids all matrices of a given class . At first an algorithm is stated for deciding whetherC can be permuted such that it avoids a set of 2×2 matrices. This approach leads to a polynomial time recognition algorithm for algebraic Monge matrices fulfilling special properties. As main result of the paper it is shown that permuted Supnick matrices can be recognized in polynomial time. Moreover, we prove that the decision problem can be solved in polynomial time, if the set is sufficiently dense, and a sparse set of 2×2 matrices is exhibited for which the decision problem is NP-complete. Eine MatrixC vermeidet eine Menge von Matrizen, wenn keine Matrix aus durch Streichen von Spalten und Zeilen vonC erhalten werden kann. In dieser Arbeit betrachten wir folgendes Entscheidungsproblem: Können die Zeilen bzw. Spalten einer MatrixC so vertauscht werden, daß die permutierte Matrix alle Matrizen aus einer gegebenen Menge vermeidet. Diese Arbeit enthält einen Algorithmus für den Fall, daß nur aus 2×2 Matrizen besteht. Dies führt zu einem polynomialen Erkennungsalgorithmus für spezielle algebraische Monge Matrizen. Als Hauptergebnis zeigen wir, daß permutierte Supnick Matrizen in polynomieller Zeit erkannt werden können. Zusätzlich wird bewiesen, daß im allgemeinen das Entscheidungsproblem NO-vollständig ist, es aber in polynomieller Zeit lösbar ist, wenn die Menge genügend dicht ist.
    Originele taal-2Engels
    Pagina's (van-tot)371-388
    Aantal pagina's18
    TijdschriftComputing
    Volume52
    Nummer van het tijdschrift4
    DOI's
    StatusGepubliceerd - 1994

    Vingerafdruk Duik in de onderzoeksthema's van 'A general approach to avoiding two by two submatrices'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit