TY - GEN
T1 - Enumerating vertices of 0/1-Polyhedra associated with 0/1-totally unimodular matrices
AU - Elbassioni, Khaled
AU - Makino, Kazuhisa
N1 - Publisher Copyright:
© Khaled Elbassioni and Kazuhisa Makino.
PY - 2018/6/1
Y1 - 2018/6/1
N2 - 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.
AB - 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.
KW - Hypergraph decomposition
KW - Hypergraph transversals
KW - Output polynomial-time algorithm
KW - Phrases totally unimodular matrices
KW - Vertex enumeration
KW - Vertices of polyhedra
UR - http://www.scopus.com/inward/record.url?scp=85049003327&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SWAT.2018.18
DO - 10.4230/LIPIcs.SWAT.2018.18
M3 - Conference contribution
AN - SCOPUS:85049003327
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 181
EP - 1814
BT - 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018
A2 - Eppstein, David
T2 - 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018
Y2 - 18 June 2018 through 20 June 2018
ER -