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

DOI DOI

Bibliographic Information

Title
Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices
Author
Khaled M. Elbassioni, Kazuhisa Makino

Description

We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron $\mathcal{P}(A,\mathbf{1})=\{x\in\RR^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.

Journal

  • LIPIcs

    LIPIcs 101 2018

    arXiv

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top