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

DOI10.1016/S0166-218X(02)00395-5MaRDI QIDQ1811083zbMATH OpenFDO

Authors Ján Plavka, M. Gavalec

Publication date 10 June 2003

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

zbMATH Keywords

eigenvalueMonge matrix

Mathematics Subject Classification ID

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

Recommendations

• Special properties of Monge matrices in max-plus algebra
• Structure of the eigenspace of a Monge matrix in max-plus algebra
• An O(n^ 2) algorithm for the maximum cycle mean of an n n bivalent matrix
• An iterative algorithm for computing the cycle mean of a Toeplitz matrix in special form
• Structure and dimension of the eigenspace of a concave Monge matrix

Cites work

• scientific article; zbMATH DE number 3906559 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3302125 (Why is no real title available?)
• A characterization of the minimum cycle mean in a digraph
• An O(n^ 2) algorithm for the maximum cycle mean of an n n bivalent matrix
• Linear and combinatorial optimization in ordered algebraic structures
• Minimax algebra
• On the Monge property of matrices
• Perspectives of Monge properties in optimization
• Recognition of \(d\)-dimensional Monge arrays
• The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices

Cited in

(18)

• Computation of the second maximum path weight in a max-plus matrix
• TheO(n3) algorithm for a special case of the maximum cost-to-time ratio cycle problem and its coherence with an eigenproblem of a matrix
• On the \(\lambda \)-robustness of matrices over fuzzy algebra
• \(\ell\)-parametric eigenproblem in max-algebra
• Eigenproblem for monotone and toeplitz matrices in a Max-algebra
• Special properties of Monge matrices in max-plus algebra
• scientific article; zbMATH DE number 3965044 (Why is no real title available?)
• Structure of the eigenspace of a Monge matrix in max-plus algebra
• Fast distance multiplication of unit-Monge matrices
• Structure and dimension of the eigenspace of a concave Monge matrix
• Fast distance multiplication of unit-Monge matrices
• An iterative algorithm for computing the cycle mean of a Toeplitz matrix in special form
• Eigenproblem for optimal-node matrices in max-plus algebra
• Tropical Vandermonde matrices
• Computing an eigenvector of a Monge matrix in max-plus algebra
• Computing an eigenvector of an inverse Monge matrix in max-plus algebra
• The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices
• On the recognition of permuted bottleneck Monge matrices

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1811083)