On the recognition of permuted bottleneck Monge matrices

B. Klinz, R. Rudolf, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)43-74
JournalDiscrete Applied Mathematics
Volume63
Issue number1
DOIs
Publication statusPublished - 1995

Fingerprint Dive into the research topics of 'On the recognition of permuted bottleneck Monge matrices'. Together they form a unique fingerprint.

Cite this