Permuting matrices to avoid forbidden submatrices
From MaRDI portal
Publication:1894366
DOI10.1016/0166-218X(94)00054-HzbMath0837.05031OpenAlexW2154919605MaRDI QIDQ1894366
Bettina Klinz, Rüdiger Rudolf, Gerhard J. Woeginger
Publication date: 23 April 1996
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(94)00054-h
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graph theory (including graph drawing) in computer science (68R10)
Related Items
A general approach to avoiding two by two submatrices, On the recognition of permuted bottleneck Monge matrices, Ferrers dimension of grid intersection graphs, On orthogonal ray graphs, Perspectives of Monge properties in optimization, Comparability digraphs: an analogue of comparability graphs, Unnamed Item, Strong Cocomparability Graphs and Slash-Free Orderings of Matrices, Enumeration of \((0.1)\)-matrices avoiding some \(2 \times 2\) matrices, On opposition graphs, coalition graphs, and bipartite permutation graphs, Bipartite Analogues of Comparability and Cocomparability Graphs, Min-Orderable Digraphs, Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs, Recognition and drawing of stick graphs, Self‐clique graphs and matrix permutations, On probe interval graphs, THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS, Strong Chordality of Graphs with Possible Loops, Large Homogeneous Submatrices, Matrix sandwich problems
Cites Work
- Monge and feasibility sequences in general flow problems
- Finding squares and rectangles in sets of points
- A linear-time algorithm for a special case of disjoint set union
- Bipartite permutation graphs
- Strong unimodularity for matrices and hypergraphs
- An algorithm for the detection and construction of Monge sequences
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- On grid intersection graphs
- Polynomial graph-colorings
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Recognition of \(d\)-dimensional Monge arrays
- A special planar satisfiability problem and a consequence of its NP- completeness
- A Monge property for the \(d\)-dimensional transportation problem
- Doubly lexical ordering of dense 0--1 matrices
- Incidence matrices and interval graphs
- A structure theorem for the consecutive 1's property
- Characterizations of totally balanced matrices
- Totally-Balanced and Greedy Matrices
- Doubly Lexical Orderings of Matrices
- Structural properties and recognition of restricted and strongly unimodular matrices
- Three Partition Refinement Algorithms
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Total Ordering Problem
- Efficient parallel algorithms for bipartite permutation graphs
- Balanced matrices
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
