Generating all vertices of a polyhedron is hard

MaRDI QIDQ3619946zbMATH OpenFDO

Authors Endre Boros, Konrad Borys, Khaled Elbassion, Leonid G. Khachiyan, Vladimir Gurvich

Publication date 14 April 2009

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Linear programming (90C05)

Recommendations

• Generating all vertices of a polyhedron is hard
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• The negative cycles polyhedron and hardness of checking some polyhedral properties
• scientific article; zbMATH DE number 5548206
• Complexity of generation

Cited in

(3)

• scientific article; zbMATH DE number 5548206 (Why is no real title available?)
• Generating all vertices of a polyhedron is hard
• The negative cycles polyhedron and hardness of checking some polyhedral properties

This page was built for publication: Generating all vertices of a polyhedron is hard

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