The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable

DOI10.1016/S0925-7721(98)00021-2zbMath0912.68206OpenAlexW1973868432MaRDI QIDQ1272311

Michael R. Bussieck, Marco E. Lübbecke

Publication date: 5 May 1999

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0925-7721(98)00021-2

zbMATH Keywords

computational complexitystrong \({\mathcal P}\)-enumerability

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints ⋮ Enumerating trichromatic triangles containing the origin in linear time ⋮ A New Algorithm for Enumeration of Cells of Hyperplane Arrangements and a Comparison with Avis and Fukuda's Reverse Search ⋮ Unnamed Item ⋮ The negative cycles polyhedron and hardness of checking some polyhedral properties ⋮ Counting Solutions of Integer Programs Using Unrestricted Subtree Detection ⋮ FINDING SIMPLICES CONTAINING THE ORIGIN IN TWO AND THREE DIMENSIONS ⋮ Efficient edge-skeleton computation for polytopes defined by oracles ⋮ Enumerating Minimal Transversals of Hypergraphs without Small Holes ⋮ Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices ⋮ Generating all vertices of a polyhedron is hard ⋮ Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices

Uses Software

• CPLEX

Cites Work

• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Primal-dual methods for vertex and facet enumeration
• Efficient enumeration of the vertices of polyhedra associated with network LP's
• Finding all the perfect matchings in bipartite graphs
• Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
• The Complexity of Enumeration and Reliability Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable