Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices
DOI10.1137/18M1198995zbMath1432.68324OpenAlexW3013368798MaRDI QIDQ5220475
Kazuhisa Makino, Khaled M. Elbassioni
Publication date: 26 March 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1198995
vertex enumerationtotally unimodular matriceshypergraph transversalshypergraph decompositionvertices of polyhedraoutput polynomial-time algorithm
Analysis of algorithms (68W40) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational aspects related to convexity (52B55) Hypergraphs (05C65) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The negative cycles polyhedron and hardness of checking some polyhedral properties
- Enumeration of Nash equilibria for two-player games
- Decomposition of regular matroids
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
- Primal-dual methods for vertex and facet enumeration
- Efficient enumeration of the vertices of polyhedra associated with network LP's
- Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
- A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
- Reverse search for enumeration
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- Complexity of identification and dualization of positive Boolean functions
- Combinatorial Optimization
- The Complexity of Vertex Enumeration Methods
- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On the width—length inequality
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- An algorithm for determining all extreme points of a convex polytope
- An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Enumerating Minimal Transversals of Hypergraphs without Small Holes
- On the Complexity of Some Enumeration Problems for Matroids
- LATIN 2004: Theoretical Informatics
- Generating all vertices of a polyhedron is hard
