A POLYNOMIAL ALGORITHM FOR ENUMERATING ALL VERTICES OF A Base Polyhedron

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³|V|) time and in O(n²) 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