Groupe d’études et de recherche en analyse des décisions


On-Line and Off-Line Vertex Enumeration by Adjacency Lists

, et

We propose a new algorithm to solve the on-line vertex enumeration problem for polytopes, doing all computations in n-space, where n is the dimension of the polytope. This algorithm exploits adjacency lists between vertices and uses no simplex tableaux. It can handle the cases of empty or degenerate polyhedra. Computational experience for off-line vertex enumeration is reported.

, 13 pages