تقرير
Polynomial time vertex enumeration of convex polytopes of bounded branch-width
| العنوان: | Polynomial time vertex enumeration of convex polytopes of bounded branch-width |
|---|---|
| المؤلفون: | Reimers, Arne C., Stougie, Leen |
| سنة النشر: | 2014 |
| المجموعة: | Computer Science Mathematics Quantitative Biology |
| مصطلحات موضوعية: | Computer Science - Computational Geometry, Computer Science - Computational Complexity, Mathematics - Combinatorics, Quantitative Biology - Molecular Networks, 52C45 (Primary), 52B40, 52B11, 68Q25 (Secondary), F.2.2, I.1.2 |
| الوصف: | Over 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. It is a famous and long standing open question in polyhedral theory and computational geometry whether the vertices of a polytope (bounded polyhedron), described by a set of linear constraints, can be enumerated in total polynomial time. In this paper we apply the concept of branch-decomposition to the vertex enumeration problem of polyhedra $P = \{x : Ax = b, x \geq 0\}$. For this purpose, we introduce the concept of $k$-module and show how it relates to the separators of the linear matroid generated by the columns of $A$. 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 $A$ is bounded by a constant $k$. Comment: 15 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1404.5584 |
| رقم الأكسشن: | edsarx.1404.5584 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |