Enumerating vertices of covering polyhedra with totally unimodular constraint matrices

Khaled Elbassioni, Kazuhisa Makino

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron P = P(A,1) = {x ∈ Rn | Ax ≥ 1, x ≥ 0}, 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.

Original languageBritish English
Pages (from-to)843-864
Number of pages22
JournalSIAM Journal on Discrete Mathematics
Volume34
Issue number1
DOIs
StatePublished - 2020

Keywords

  • Hypergraph decomposition
  • Hypergraph transversals
  • Output polynomial time algorithm
  • Totally unimodular matrices
  • Vertex enumeration
  • Vertices of polyhedra

Fingerprint

Dive into the research topics of 'Enumerating vertices of covering polyhedra with totally unimodular constraint matrices'. Together they form a unique fingerprint.

Cite this