Permuting matrices to avoid forbidden submatrices
type: Item
instance of: scholarly article
title: Permuting matrices to avoid forbidden submatrices
zbMATH Open document ID: 0837.05031
DOI: 10.1016/0166-218X(94)00054-H
author: Bettina Klinz
author: Rüdiger Rudolf
author: Gerhard J. Woeginger
published in: Discrete Applied Mathematics
publication date: 1996-04-23T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 777827
zbMATH Keywords: permuting matrices
zbMATH Keywords: forbidden submatrices
zbMATH Keywords: \((0,1)\)-matrices
zbMATH Keywords: algorithmic complexity
reviewed by: Kishore Sinha
MaRDI profile type: Publication
cites work: Monge and feasibility sequences in general flow problems
cites work: An algorithm for the detection and construction of Monge sequences
cites work: Characterizations of totally balanced matrices
cites work: A Monge property for the \(d\)-dimensional transportation problem
cites work: Q3893826
cites work: Q3956745
cites work: Balanced matrices
cites work: Q4099676
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Q4191842
cites work: Efficient parallel algorithms for bipartite permutation graphs
cites work: Structural properties and recognition of restricted and strongly unimodular matrices
cites work: Strong unimodularity for matrices and hypergraphs
cites work: Finding squares and rectangles in sets of points
cites work: Incidence matrices and interval graphs
cites work: A linear-time algorithm for a special case of disjoint set union
cites work: Q4198056
cites work: Q3328583
cites work: Polynomial graph-colorings
cites work: On grid intersection graphs
cites work: Q5557602
cites work: Q3737235
cites work: Totally-Balanced and Greedy Matrices
cites work: A special planar satisfiability problem and a consequence of its NP- completeness
cites work: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
cites work: Doubly Lexical Orderings of Matrices
cites work: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
cites work: Q3912037
cites work: Total Ordering Problem
cites work: Three Partition Refinement Algorithms
cites work: Recognition of \(d\)-dimensional Monge arrays
cites work: Doubly lexical ordering of dense 0--1 matrices
cites work: Bipartite permutation graphs
cites work: A structure theorem for the consecutive 1's property
full work available at URL: 0166-218x(94)00054-h
OpenAlex ID: W2154919605
Recommended article: Matrices with forbidden subconfigurations
Recommended article: Posets of matrices and permutations with forbidden subsequences
Recommended article: Permutation (Matrices) and Beyond
Recommended article: Q5417768
Recommended article: Permutations matrix
Recommended article: On the matrix permutation problem
Recommended article: On compound permutation matrices
Recommended article: SOFSEM 2004: Theory and Practice of Computer Science
Recommended article: Q5090530
Recommended article: Solving a family of permutation problems on 0-1 matrices
description: scientific article; zbMATH DE number 777827