𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the monge property of matrices

✍ Scribed by Katarína Cechlárová; Peter Szabó

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
307 KB
Volume
81
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A square matrix A = (aij) over a commutative linearly ordered group (G, *, s) is said to have the Monge property if aii * ay < aij *ski holds for all i and for all j, k > i. We present an O(n4) algorithm for checking whether the rows and columns of a given matrix can be permuted in such a way that the obtained matrix has the Monge property.

📜 SIMILAR VOLUMES

Computing a Minimum Weightk-Link Path in
Computing a Minimum Weightk-Link Path in Graphs with the Concave Monge Property
✍ Baruch Schieber 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 233 KB

Let G be a weighted, complete, directed acyclic graph whose edge weights obey the concave Monge condition. We give an efficient algorithm for finding the minimum weight k-link path between a given pair of vertices for any given k. The time, for k s ⍀ log n . Our algorithm can be applied to get effi