A POLYNOMIAL ALGORITHM FOR ENUMERATING ALL VERTICES OF A BASE POLYHEDRON

DOI10.15807/JORSJ.40.329MaRDI QIDQ4366145zbMATH OpenOpenAlexFDO

Authors Ping Zhan

Publication date 7 September 1998

Published in Journal of the Operations Research Society of Japan (Search for Journal in Brave)

Full work available at URL https://doi.org/10.15807/jorsj.40.329

zbMATH Keywords

polynomial algorithmenumeration of all verticessubmodular base polyhedron

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Recommendations

• A new algorithm to find all vertices of a polytope
• An algorithm for enumeration of polyhedra and orbifolds
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• scientific article; zbMATH DE number 1741017
• Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
• Numerical algorithm for Pólya enumeration theorem
• Efficient enumeration of the vertices of polyhedra associated with network LP's
• An efficient algorithm for enumeration of triangulations

Cited in

(7)

• A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization
• Enumerating integer points in polytopes with bounded subdeterminants
• Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
• scientific article; zbMATH DE number 2040941 (Why is no real title available?)
• Enumerating vertices of \(0/1\)-polyhedra associated with \(0/1\)-totally unimodular matrices

This page was built for publication: A POLYNOMIAL ALGORITHM FOR ENUMERATING ALL VERTICES OF A BASE POLYHEDRON

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4366145)