Recognition of \(d\)-dimensional Monge arrays

DOI10.1016/0166-218X(92)00189-SzbMath0819.90060OpenAlexW2013345559MaRDI QIDQ1329798

Rüdiger Rudolf

Publication date: 31 July 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(92)00189-s

zbMATH Keywords

permutationsMonge array\(d\)-dimensional axial transportation assignment problem

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items

Permuting matrices to avoid forbidden submatrices ⋮ Supermodular functions and the complexity of MAX CSP ⋮ On the recognition of permuted bottleneck Monge matrices ⋮ The assignment problem with nearly Monge arrays and incompatible partner indices ⋮ Efficiently solvable special cases of hard combinatorial optimization problems ⋮ Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon ⋮ On Monge sequences in \(d\)-dimensional arrays ⋮ Perspectives of Monge properties in optimization ⋮ Estimation of Monge matrices ⋮ A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs ⋮ An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.

Cites Work

• On the Monge property of matrices
• An algorithm for the detection and construction of Monge sequences
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A Monge property for the \(d\)-dimensional transportation problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item