THE VERTEX SET OF A 0 1-POLYTOPE IS STRONGLY P-ENUMERABLE/

In this paper, we discuss the computational complexity of the followin g enumeration problem: given a rational convex polyhedron P defined by a system of linear inequalities, output each vertex of P. It is still an open question whether there exists an algorithm for listing all ve rtices in running time polynomial in the input size and the output siz e. Informally speaking, a linear running time in the output size leads to the notion of P-enumerability introduced by Valiant (1979). The co ncept of strong p-enumerability additionally requires an output indepe ndent space complexity of the respective algorithm. We give such an al gorithm for polytopes all of whose vertices are among the vertices of a polytope combinatorially equivalent to the hypercube. As a very impo rtant special case, this class of polytopes contains all 0/1-polytopes . Our implementation based on the commercial LP solver CPLEX1 is super ior to general vertex enumeration algorithms. We give an example how s implifications of our algorithm lead to efficient enumeration of combi natorial objects, (C) 1998 Elsevier Science B.V. All rights reserved.