Permuting matrices to avoid forbidden submatrices
From MaRDI portal
Publication:1894366
DOI10.1016/0166-218X(94)00054-HzbMATH Open0837.05031OpenAlexW2154919605MaRDI QIDQ1894366FDOQ1894366
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
Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Incidence matrices and interval graphs
- A linear-time algorithm for a special case of disjoint set union
- Doubly lexical ordering of dense 0--1 matrices
- Three Partition Refinement Algorithms
- Bipartite permutation graphs
- Characterizations of totally balanced matrices
- A special planar satisfiability problem and a consequence of its NP- completeness
- Total Ordering Problem
- Totally-Balanced and Greedy Matrices
- Doubly Lexical Orderings of Matrices
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- Recognition of \(d\)-dimensional Monge arrays
- A Monge property for the \(d\)-dimensional transportation problem
- Balanced matrices
- On grid intersection graphs
- Polynomial graph-colorings
- An algorithm for the detection and construction of Monge sequences
- A structure theorem for the consecutive 1's property
- Finding squares and rectangles in sets of points
- Strong unimodularity for matrices and hypergraphs
- Structural properties and recognition of restricted and strongly unimodular matrices
- Efficient parallel algorithms for bipartite permutation graphs
- Monge and feasibility sequences in general flow problems
Cited In (25)
- Recognition and drawing of stick graphs
- Solving a family of permutation problems on 0-1 matrices
- Title not available (Why is that?)
- On opposition graphs, coalition graphs, and bipartite permutation graphs
- Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
- On probe interval graphs
- Matrix sandwich problems
- On orthogonal ray graphs
- Enumeration of \((0.1)\)-matrices avoiding some \(2 \times 2\) matrices
- Comparability digraphs: an analogue of comparability graphs
- Recovering single-crossing preferences from approval ballots
- Bipartite Analogues of Comparability and Cocomparability Graphs
- Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
- Ferrers dimension of grid intersection graphs
- A general approach to avoiding two by two submatrices
- Perspectives of Monge properties in optimization
- On the matrix permutation problem
- Large Homogeneous Submatrices
- Remarks on ‘equivalence of stability concepts for discrete time-varying systems’
- Self‐clique graphs and matrix permutations
- THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
- Min-Orderable Digraphs
- On the recognition of permuted bottleneck Monge matrices
- Strong Chordality of Graphs with Possible Loops
- SOFSEM 2004: Theory and Practice of Computer Science
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Posets of matrices and permutations with forbidden subsequences 👍 👎
- On compound permutation matrices 👍 👎
- SOFSEM 2004: Theory and Practice of Computer Science 👍 👎
- Permutation (Matrices) and Beyond 👍 👎
- Matrices with forbidden subconfigurations 👍 👎
- Permutations matrix 👍 👎
- Solving a family of permutation problems on 0-1 matrices 👍 👎
- On the matrix permutation problem 👍 👎
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)
