The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices

DOI10.1080/02331939408843990zbMATH Open0815.68080OpenAlexW1983281467MaRDI QIDQ4764873FDOQ4764873

Authors: Ján Plavka 

Publication date: 30 June 1995

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331939408843990

Recommendations

• An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix
• An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.
• scientific article; zbMATH DE number 2104735
• On the computation of maximum minors of Hadamard matrices
• On the approximability of the minimum strictly fundamental cycle basis problem
• On the complexity of approximating extremal determinants in matrices
• Tight bounds on the number of minimum-mean cycle cancellations and related results
• scientific article; zbMATH DE number 2089223
• On the dependence of the maximum cycle mean of a matrix on permutations of the rows and columns
• The minimum rank problem for circulants

zbMATH Keywords

matricesmaximum cycle mean

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (8)

• The robustness of interval matrices in max-plus algebra
• On Eigenproblem for Circulant Matrices in Max-Algebra
• \(\ell\)-parametric eigenproblem in max-algebra
• Permuted max-algebraic eigenvector problem is \(NP\)-complete
• The weak robustness of interval matrices in max-plus algebra
• On the dependence of the maximum cycle mean of a matrix on permutations of the rows and columns
• An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.
• Title not available (Why is that?)

This page was built for publication: The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices

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