An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.

DOI10.1016/S0166-218X(02)00395-5zbMath1041.90045MaRDI QIDQ1811083

Ján Plavka, Martin Gavalec

Publication date: 10 June 2003

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

zbMATH Keywords

eigenvalueMonge matrix

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (9)

Tropical Vandermonde matrices ⋮ Eigenproblem for optimal-node matrices in max-plus algebra ⋮ Computing an eigenvector of an inverse Monge matrix in max-plus algebra ⋮ On the \(\lambda \)-robustness of matrices over fuzzy algebra ⋮ Computing an eigenvector of a Monge matrix in max-plus algebra ⋮ Structure of the eigenspace of a Monge matrix in max-plus algebra ⋮ Eigenproblem for monotone and toeplitz matrices in a Max-algebra ⋮ Structure and dimension of the eigenspace of a concave Monge matrix ⋮ \(\ell\)-parametric eigenproblem in max-algebra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Monge property of matrices
• Linear and combinatorial optimization in ordered algebraic structures
• An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix
• A characterization of the minimum cycle mean in a digraph
• Minimax algebra
• Recognition of \(d\)-dimensional Monge arrays
• Perspectives of Monge properties in optimization
• The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices

This page was built for publication: An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.