An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix

DOI10.1016/0166-218X(92)90039-DzbMath0776.05070OpenAlexW2021936731MaRDI QIDQ1183336

Peter Butkovic, Raymond Cuninghame-Green

Publication date: 28 June 1992

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

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

zbMATH Keywords

complexityreal matrixmaximum cycle meanbivalent matrix

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20)

Related Items

On Eigenproblem for Circulant Matrices in Max-Algebra ⋮ Extremal eigenproblem for bivalent matrices ⋮ The complexity of mean payoff games on graphs ⋮ Eigenproblem for optimal-node matrices in max-plus algebra ⋮ Maximum cycle-means of weighted digraphs ⋮ Eigenproblem for monotone and toeplitz matrices in a Max-algebra ⋮ Approximating the minimum cycle mean ⋮ An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra. ⋮ \(\ell\)-parametric eigenproblem in max-algebra ⋮ Strong regularity of matrices -- a survey of results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal cycles in doubly weighted graphs and approximation of bivariate functions by univariate ones
• On the dependence of the maximum cycle mean of a matrix on permutations of the rows and columns
• A characterization of the minimum cycle mean in a digraph