A general approach to avoiding two by two submatrices

DOI10.1007/BF02276883zbMath0804.05014OpenAlexW2104979271MaRDI QIDQ1332690

Rüdiger Rudolf, Gerhard J. Woeginger, Vladimir G. Deǐneko

Publication date: 1 September 1994

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02276883

zbMATH Keywords

NP-completedecision problemmatrixMonge matricespolynomial time recognition algorithmSupnick matrices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorics in computer science (68R05) Permutations, words, matrices (05A05)

Related Items

Comparability digraphs: an analogue of comparability graphs ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs

Cites Work

• Extreme Hamiltonian lines
• Polynomial graph-colorings
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• Permuting matrices to avoid forbidden submatrices
• Special cases of travelling salesman problems and heuristics
• Universal conditions for algebraic travelling salesman problems to be efficiently solvable
• Totally-Balanced and Greedy Matrices
• Doubly Lexical Orderings of Matrices
• Three Partition Refinement Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item