TY - JOUR

T1 - On the recognition of permuted bottleneck Monge matrices

AU - Klinz, B.

AU - Rudolf, R.

AU - Woeginger, G.J.

PY - 1995

Y1 - 1995

N2 - An n × m matrix A is called bottleneck Monge matrix if max{aij, ars} max{aij, arj} for all 1 i <r n, 1 j <s m. The matrix A is termed permuted bottleneck Monge matrix, if there exist row and column permutations such that the permuted matrix becomes a bottleneck Monge matrix.
We first deal with the special case of 0–1 bottleneck Monge matrices. Next, we derive several fundamental properties on the combinatorial structure of bottleneck Monge matrices with arbitrary entries. As a main result we show that permuted bottleneck Monge matrices with arbitrary entries can be recognized in O(nm(n + m)) time.

AB - An n × m matrix A is called bottleneck Monge matrix if max{aij, ars} max{aij, arj} for all 1 i <r n, 1 j <s m. The matrix A is termed permuted bottleneck Monge matrix, if there exist row and column permutations such that the permuted matrix becomes a bottleneck Monge matrix.
We first deal with the special case of 0–1 bottleneck Monge matrices. Next, we derive several fundamental properties on the combinatorial structure of bottleneck Monge matrices with arbitrary entries. As a main result we show that permuted bottleneck Monge matrices with arbitrary entries can be recognized in O(nm(n + m)) time.

U2 - 10.1016/0166-218X(94)00019-A

DO - 10.1016/0166-218X(94)00019-A

M3 - Article

VL - 63

SP - 43

EP - 74

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1

ER -