Exploring the complexity of the integer image problem in the \(\max\)-algebra

DOI10.1016/j.dam.2016.09.016zbMath1362.15022OpenAlexW2521294973MaRDI QIDQ516821

Marie MacCaig

Publication date: 15 March 2017

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

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

zbMATH Keywords

complexityimage space\(\max\)-algebracolumn spaninteger image probleminteger vector

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical bifurcation problems (65P30) Max-plus and related algebras (15A80)

Related Items

On integer images of max-plus linear mappings, Approximating the volume of tropical polytopes is difficult

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the integer max-linear programming problem
• A characterization of the minimum cycle mean in a digraph
• On integer eigenvectors and subeigenvectors in the max-plus algebra
• XSAT and NAE-SAT of linear CNF classes
• Permuted max-algebraic eigenvector problem is \(NP\)-complete
• Max-linear Systems: Theory and Algorithms
• The complexity of satisfiability problems