Computing the vertices of tropical polyhedra using directed hypergraphs

DOI10.1007/s00454-012-9469-6zbMath1312.52001arXiv0904.3436OpenAlexW2005348468MaRDI QIDQ1943657

Xavier Allamigeon, Stéphane Gaubert, Eric Goubault

Publication date: 20 March 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0904.3436

zbMATH Keywords

tropical geometrydirected hypergraphstropical convexityvertex enumeration problem

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Hypergraphs (05C65) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Axiomatic and generalized convexity (52A01) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Weighted digraphs and tropical cones ⋮ Weakly linear systems for matrices over the max-plus quantale ⋮ \(\mathbf{X}\)-simple image eigencones of tropical matrices ⋮ Tropicalizing the Simplex Algorithm ⋮ An improved algorithm for finding the generators of the solution space for \(A\otimes \mathbf{x}\ge \mathbf{x} \) ⋮ Tropical Fourier–Motzkin elimination, with an application to real-time verification ⋮ Tropicalization of facets of polytopes ⋮ Extreme rays of the \(\ell^\infty\)-nearest ultrametric tropical polytope ⋮ A contribution to the determinization of max-plus automata ⋮ On the dimension of max-min convex sets ⋮ A characterization of bases of tropical kernels in terms of Cramer's rule ⋮ Extremality criteria for the supereigenvector space in max-plus algebra ⋮ Tropical Carathéodory with matroids ⋮ Face posets of tropical polyhedra and monomial ideals ⋮ Minimal half-spaces and external representation of tropical polyhedra ⋮ On two-sided max-linear equations ⋮ On the complexity of strongly connected components in directed hypergraphs ⋮ On \(2 \times 2\) tropical commuting matrices ⋮ On Special Cases of the Generalized Max-Plus Eigenproblem ⋮ On tropical Kleene star matrices and alcoved polytopes ⋮ Extremals of the supereigenvector cone in max algebra: a combinatorial description ⋮ Conditional independence in max-linear Bayesian networks

Uses Software

• polymake
• Maxplus
• TPLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of strongly connected components in directed hypergraphs
• An algorithm to describe the solution set of any tropical linear system \(A \odot x = B \odot x\)
• Tropical polar cones, hypergraph transversals, and mean payoff games
• The number of extreme points of tropical polyhedra
• Minimal half-spaces and external representation of tropical polyhedra
• The Minkowski theorem for max-plus convex sets
• Generators, extremals and bases of max cones
• A decomposition formula of idempotent polyhedral cones based on idempotent superharmonic spaces
• Hard problems in max-algebra, control theory, hypergraphs and other areas
• A \(\mathbb B\)-convex production model for evaluating performance of firms
• Minimax algebra
• Duality and separation theorems in idempotent semimodules.
• Directed hypergraphs and applications
• Max-algebra: The linear algebra of combinatorics?
• Tropical convexity
• Carathéodory, Helly and the others in the max-plus world
• Tropical hyperplane arrangements and oriented matroids
• Tropical convexity via cellular resolutions
• TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
• Duality Between Invariant Spaces for Max-Plus Linear Discrete Event Systems
• Linear independence over tropical semirings and beyond
• Tropical Convex Hull Computations
• Non-archimedean amoebas and tropical varieties
• Inferring Min and Max Invariants Using Max-Plus Polyhedra
• Max-linear Systems: Theory and Algorithms
• Worst-case Analysis of Set Union Algorithms
• On Finding the Maxima of a Set of Vectors
• -convexity
• The tropical Grassmannian
• Methods and applications of (max,+) linear algebra
• Max-Plus $(A,B)$-Invariant Spaces and Control of Timed Discrete-Event Systems
• Affine Buildings and Tropical Convexity
• Tropical Polytopes and Cellular Resolutions
• Max-Plus Convex Geometry
• The maximum numbers of faces of a convex polytope
• Max-plus convex sets and max-plus semispaces. I
• Idempotent functional analysis: An algebraic approach