Permuting matrices to avoid forbidden submatrices

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

zbMATH Keywords

algorithmic complexity\((0,1)\)-matricesforbidden submatricespermuting matrices

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graph theory (including graph drawing) in computer science (68R10)

Related Items (20)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Permuting matrices to avoid forbidden submatrices