Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices
Khaled Elbassioni, Kazuhisa Makino · SIAM Journal on Discrete Mathematics · 2020
We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron $P=P(A,\b1)=\{x\in \mathbb{R}^n \mid Ax\geq \b1,~x\geq \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.