Hard problems in max-algebra, control theory, hypergraphs and other areas

DOI10.1016/J.IPL.2009.11.007MaRDI QIDQ990130zbMATHOpenAlexFDO

Authors 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

zbMATH Keywords

algorithmscomputational complexityconstraint solving(hyper)graphs

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Control/observation systems involving computers (process control, etc.) (93C83)

Cites work

• A strongly polynomial algorithm for solving two-sided linear systems in max-algebra
• Directed hypergraphs and applications
• Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra
• Min-max functions
• On-line computation of minimal and maximal length paths
• Positional strategies for mean payoff games
• Scheduling with AND/OR Precedence Constraints
• Solving SAT and SAT modulo theories, from an abstract Davis-Putnam-Logemann-Loveland procedure to \(\operatorname{DPLL}(T)\)
• The Max-Atom Problem and Its Relevance

Cited in

(12)

• Geometric Quantifier Elimination Heuristics for Automatically Generating Octagonal and Max-plus Invariants
• Computing the vertices of tropical polyhedra using directed hypergraphs
• Tropical linear-fractional programming and parametric mean payoff games
• On special cases of the generalized max-plus eigenproblem
• Tropical polyhedra are equivalent to mean payoff games
• A note on tropical linear and integer programs
• Tropical Cryptography
• New algorithms for solving tropical linear systems
• Complexity of tropical and MIN-plus linear prevarieties
• A strongly polynomial method for solving integer max-linear optimization problems in a generic case
• Extremality criteria for the supereigenvector space in max-plus algebra
• Tropical polar cones, hypergraph transversals, and mean payoff games

This page was built for publication: Hard problems in max-algebra, control theory, hypergraphs and other areas

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