On the recognition of permuted bottleneck Monge matrices (Q1902890)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the recognition of permuted bottleneck Monge matrices |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the recognition of permuted bottleneck Monge matrices |
scientific article |
Statements
On the recognition of permuted bottleneck Monge matrices (English)
0 references
4 July 1996
0 references
A rectangular matrix is called a bottleneck Monge matrix if for every \(2\times 2\) submatrix the larger entry on the main diagonal does not exceed the larger entry on the skew diagonal. The main result is that the complexity of recognizing if an \(n\times m\) \((0, 1)\)-matrix is permutable to a bottleneck Monge matrix is of order \(O(nm(n+ m))\).
0 references
recognition
0 references
rectangular matrix
0 references
bottleneck Monge matrix
0 references
0 references
0 references
0 references
