In the last years the vertex enumeration problem of polyhedra has seen a revival in the study of metabolic networks, which increased the demand for efficient vertex enumeration algorithms for high-dimensional polyhedra given by inequalities. In this paper we apply the concept of branch-decomposition to the vertex enumeration problem of polyhedra P={x:Sx=b,x≥0}. Therefore, we introduce the concept of k-module and show how it relates to the separators of the linear matroid generated by the columns of S. This then translates structural properties of the matroidal branch-decomposition to the context of polyhedra. We then use this to present a total polynomial time algorithm for polytopes P for which the branch-width of the linear matroid generated by S is bounded by a constant k.
Additional Metadata
THEME Null option (theme 11)
Publisher Cornell University Library
Series arXiv.org e-Print archive
Citation
Reimers, A.C, & Stougie, L. (2015). A decomposition theory for vertex enumeration of convex polyhedra. arXiv.org e-Print archive. Cornell University Library.