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 -