Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices

2017/07/12 by Elbassioni, Khaled, Makino, Kazuhisa
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1707.03914

Abstract

We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron P(A,1)=\x∈\RRⁿ | Ax≥ \b1,~x≥ \b0\, when A is a totally unimodular matrix. Our algorithm is based on decomposing the hypergraph transversal problem for unimodular hypergraphs using Seymour's decomposition of totally unimodular matrices, and may be of independent interest.

Related

• Unimodular polytopes and column number bounds on polytopal totally unimodular matrices via Seymour's decomposition theorem
• Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
• Polynomial time vertex enumeration of convex polytopes of bounded branch-width
• Upper Bound on the Number of Vertices of Polyhedra with 0,1-Constraint Matrices
• Enumerating integer points in polytopes with bounded subdeterminants