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

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

Peter Butkovic, Raymond Cuninghame-Green

Publication date: 28 June 1992

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

zbMATH Keywords

complexity; real matrix; maximum cycle mean; bivalent matrix

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C20: Directed graphs (digraphs), tournaments

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item