Hard problems in max-algebra, control theory, hypergraphs and other areas
From MaRDI portal
Publication:990130
DOI10.1016/j.ipl.2009.11.007zbMath1206.68284MaRDI QIDQ990130
Marc Bezem, Robert Nieuwenhuis, Enric Rodríguez-Carbonell
Publication date: 2 September 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2009.11.007
68Q25: Analysis of algorithms and problem complexity
68W05: Nonnumerical algorithms
93C83: Control/observation systems involving computers (process control, etc.)
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Geometric Quantifier Elimination Heuristics for Automatically Generating Octagonal and Max-plus Invariants, New algorithms for solving tropical linear systems, Tropical Cryptography, Tropical linear-fractional programming and parametric mean payoff games, Tropical polar cones, hypergraph transversals, and mean payoff games, A note on tropical linear and integer programs, Computing the vertices of tropical polyhedra using directed hypergraphs, A strongly polynomial method for solving integer max-linear optimization problems in a generic case, Complexity of tropical and MIN-plus linear prevarieties, Extremality criteria for the supereigenvector space in max-plus algebra, On Special Cases of the Generalized Max-Plus Eigenproblem, TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
Cites Work
- Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra
- Positional strategies for mean payoff games
- On-line computation of minimal and maximal length paths
- Min-max functions
- Directed hypergraphs and applications
- A strongly polynomial algorithm for solving two-sided linear systems in max-algebra
- Solving SAT and SAT Modulo Theories
- Scheduling with AND/OR Precedence Constraints
- The Max-Atom Problem and Its Relevance