Permuting matrices to avoid forbidden submatrices
From MaRDI portal
The authors survey several known and new results on the algorithmic complexity of the problem of deciding whether the rows and columns of a matrix can be permuted in such a way that the resulting matrix \(M\) avoids all matrices in \({\mathcal F}\), a fixed set of matrices.
Recommendations
- Matrices with forbidden subconfigurations
- Posets of matrices and permutations with forbidden subsequences
- Permutation (Matrices) and Beyond
- Matrices with forbidden submatrices
- Permutations matrix
- On the matrix permutation problem
- On compound permutation matrices
- SOFSEM 2004: Theory and Practice of Computer Science
- Blockers of pattern avoiding permutation matrices
- Solving a family of permutation problems on 0-1 matrices
Cites work
- A linear-time algorithm for a special case of disjoint set union
- A Monge property for the \(d\)-dimensional transportation problem
- A special planar satisfiability problem and a consequence of its NP- completeness
- A structure theorem for the consecutive 1's property
- An algorithm for the detection and construction of Monge sequences
- Balanced matrices
- Bipartite permutation graphs
- Characterizations of totally balanced matrices
- Doubly lexical ordering of dense 0--1 matrices
- Doubly Lexical Orderings of Matrices
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- Efficient parallel algorithms for bipartite permutation graphs
- Finding squares and rectangles in sets of points
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3970528 (Why is no real title available?)
- scientific article; zbMATH DE number 3700728 (Why is no real title available?)
- scientific article; zbMATH DE number 3723879 (Why is no real title available?)
- scientific article; zbMATH DE number 3777260 (Why is no real title available?)
- scientific article; zbMATH DE number 3522018 (Why is no real title available?)
- scientific article; zbMATH DE number 3630467 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3272833 (Why is no real title available?)
- Incidence matrices and interval graphs
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Monge and feasibility sequences in general flow problems
- On grid intersection graphs
- Polynomial graph-colorings
- Recognition of \(d\)-dimensional Monge arrays
- Strong unimodularity for matrices and hypergraphs
- Structural properties and recognition of restricted and strongly unimodular matrices
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Three Partition Refinement Algorithms
- Total Ordering Problem
- Totally-Balanced and Greedy Matrices
Cited in
(28)- On probe interval graphs
- Matrix sandwich problems
- A general approach to avoiding two by two submatrices
- On the recognition of permuted bottleneck Monge matrices
- Perspectives of Monge properties in optimization
- On opposition graphs, coalition graphs, and bipartite permutation graphs
- Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
- Defragmentation of permutation tables with four columns
- THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
- Ferrers dimension of grid intersection graphs
- Obtaining a triangular matrix by independent row-column permutations
- On the matrix permutation problem
- Solving a family of permutation problems on 0-1 matrices
- Remarks on ‘equivalence of stability concepts for discrete time-varying systems’
- Enumeration of (0.1)-matrices avoiding some 2 2 matrices
- Self‐clique graphs and matrix permutations
- Interval-like graphs and digraphs
- Bipartite Analogues of Comparability and Cocomparability Graphs
- Min-orderable digraphs
- Strong Chordality of Graphs with Possible Loops
- Large homogeneous submatrices
- SOFSEM 2004: Theory and Practice of Computer Science
- On orthogonal ray graphs
- Comparability digraphs: an analogue of comparability graphs
- Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
- Recovering single-crossing preferences from approval ballots
- On supmodular matrices
- On geometric bipartite graphs with asymptotically smallest Zarankiewicz numbers
This page was built for publication: Permuting matrices to avoid forbidden submatrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894366)
