Enumerating vertices of polyhedra and related generating problems

by Endre Boros

Generating vertices of polyhedra is an old problem, with
several algorithmic ideas in the literature, each known
to work efficiently for some particular types of polyhedra.
In this talk we survey several related generation problems
of polyhedral geometry and graph theory, and prove the
hardness of some of these, including vertex enumeration of
polyhedra. (Joint results with K. Borys, K. Elbassioni,
V. Gurvich,  and  L. Khachiyan.)