Efficient enumeration of the vertices of polyhedra associated with network LP's

DOI10.1007/BF01582058zbMath0792.90045MaRDI QIDQ1315430

J. Scott Provan

Publication date: 10 March 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

enumerationgenerationlistingnetwork linear programsvertices of polyhedra

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints, How good are convex hull algorithms?, Unnamed Item, The negative cycles polyhedron and hardness of checking some polyhedral properties, Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices, Generating all vertices of a polyhedron is hard, The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable, A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• An algorithm for enumerating all vertices of a convex polyhedron
• A paradigm for listing \((s,t)\)-cuts in graphs
• Finding all vertices of a convex polyhedron
• The Complexity of Vertex Enumeration Methods
• Finding the convex hull facet by facet
• An Algorithm for Finding All Vertices of Convex Polyhedral Sets
• A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Technical Note—Vertex Generation and Cardinality Constrained Linear Programs
• An algorithm for determining all extreme points of a convex polytope
• An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities