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 language | British English |
|---|---|
| Pages (from-to) | 843-864 |
| Number of pages | 22 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 34 |
| Issue number | 1 |
| DOIs | |
| State | Published - 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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver