Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices
From MaRDI portal
Publication:5116482
DOI10.4230/LIPIcs.SWAT.2018.18zbMath1477.68467arXiv1707.03914OpenAlexW2964248860MaRDI QIDQ5116482
Kazuhisa Makino, Khaled M. Elbassioni
Publication date: 25 August 2020
Full work available at URL: https://arxiv.org/abs/1707.03914
vertex enumerationtotally unimodular matriceshypergraph transversalshypergraph decompositionvertices of polyhedraoutput polynomial-time algorithm
Analysis of algorithms (68W40) Factorization of matrices (15A23) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Hypergraphs (05C65) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Matrices of integers (15B36)
Related Items
Cites Work
- 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
- How good are convex hull algorithms?
- Reverse search for enumeration
- 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
- 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
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- On the Complexity of Some Enumeration Problems for Matroids
- Generating all vertices of a polyhedron is hard
