A general approach to avoiding two by two submatrices

DOI10.1007/BF02276883MaRDI QIDQ1332690zbMATH OpenOpenAlexFDO

Authors Rüdiger Rudolf, Gerhard J. Woeginger, Vladimir G. Deineko

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

decision problemmatrixMonge matricesNP-completepolynomial time recognition algorithmSupnick matrices

Mathematics Subject Classification ID

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

Recommendations

• Permuting matrices to avoid forbidden submatrices
• On the recognition of permuted bottleneck Monge matrices
• On the recognition of permuted Supnick and incomplete Monge matrices
• On nonlinear forbidden 0--1 matrices, a refutation of a Füredi-Hajnal conjecture
• scientific article; zbMATH DE number 2186901

Cites work

• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• Doubly Lexical Orderings of Matrices
• Extreme Hamiltonian lines
• scientific article; zbMATH DE number 3887060 (Why is no real title available?)
• scientific article; zbMATH DE number 3727583 (Why is no real title available?)
• scientific article; zbMATH DE number 3777260 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Permuting matrices to avoid forbidden submatrices
• Polynomial graph-colorings
• Special cases of travelling salesman problems and heuristics
• Three Partition Refinement Algorithms
• Totally-Balanced and Greedy Matrices
• Universal conditions for algebraic travelling salesman problems to be efficiently solvable

Cited in

(4)

• On the recognition of permuted bottleneck Monge matrices
• Bipartite Analogues of Comparability and Cocomparability Graphs
• SOFSEM 2004: Theory and Practice of Computer Science
• Comparability digraphs: an analogue of comparability graphs

This page was built for publication: A general approach to avoiding two by two submatrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1332690)