Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra

DOI10.1016/j.dam.2008.03.016zbMath1178.68637OpenAlexW2095082073MaRDI QIDQ1003740

Robert Nieuwenhuis, Marc Bezem, Enric Rodríguez-Carbonell

Publication date: 4 March 2009

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

Full work available at URL: https://doi.org/10.1016/j.dam.2008.03.016

zbMATH Keywords

polynomial algorithmmax-algebrastwo-sided equations

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Nonnumerical algorithms (68W05)

Related Items (8)

TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES ⋮ Log-Barrier Interior Point Methods Are Not Strongly Polynomial ⋮ On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations ⋮ Complexity of solving tropical linear systems ⋮ What Tropical Geometry Tells Us about the Complexity of Linear Programming ⋮ Hard problems in max-algebra, control theory, hypergraphs and other areas ⋮ Quantitative simulations by matrices ⋮ Unnamed Item

Cites Work

• A strongly polynomial algorithm for solving two-sided linear systems in max-algebra

This page was built for publication: Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra