On the complexity of computing the diameter of a polytope

DOI10.1007/BF01206636MaRDI QIDQ1337144zbMATH OpenOpenAlexFDO

Authors Shang-Hua Teng, Alan Frieze

Publication date 30 October 1994

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01206636

zbMATH Keywords

combinatorial diameter of a polytope

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Linear programming (90C05)

Recommendations

• Recent results around the diameter of polyhedra
• Upper bounds for the diameter and height of graphs of convex polyhedra
• Diameter of polyhedra: limits of abstraction
• Diameter of polyhedra: limits of abstraction

Cites work

• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• scientific article; zbMATH DE number 3850828 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Paths on Polytopes
• Polytope pairs and their relationship to linear programming
• The complexity of facets (and some facets of complexity)
• The polynomial-time hierarchy

Cited in

(8)

• The complexity of facets (and some facets of complexity)
• On the complexity of some basic problems in computational convexity. I. Containment problems
• Complexity yardsticks for \(f\)-vectors of polytopes and spheres
• Shortest reconfiguration of perfect matchings via alternating cycles
• Pivot rules for circuit-augmentation algorithms in linear optimization
• On the hardness of short and sign-compatible circuit walks
• Hardness of finding combinatorial shortest paths on graph associahedra
• The hardness of monotone eccentricity on polytopes

This page was built for publication: On the complexity of computing the diameter of a polytope

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