A POLYNOMIAL ALGORITHM FOR ENUMERATING ALL VERTICES OF A BASE POLYHEDRON
Ping Zhan · Journal of the Operations Research Society of Japan · 1997
In general, it is difficult to enumerate all vertices of a polytope in polynomial time. Here we present a polynomial algorithm which enumerates all vertices of a submodular base polyhedron in O(n^3|V|) time and in O(n^2) space, where V is the vertex set of a base polyhedron and n the dimension of the underlying Euclidean space. Our algorithm is also polynomial delay, and a generalization of several enumeration algorithms.