On the complexity of computing the diameter of a polytope

DOI10.1007/BF01206636zbMath0824.68042OpenAlexW2010362899MaRDI QIDQ1337144

Shang-Hua Teng, Alan M. 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) Linear programming (90C05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of facets (and some facets of complexity)
• Polytope pairs and their relationship to linear programming
• The polynomial-time hierarchy
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Paths on Polytopes

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