Diameter of Polyhedra: Limits of Abstraction

Diameter of Polyhedra: Limits of Abstraction

0.00 Avg rating0 Votes
Article ID: iaor20108767
Volume: 35
Issue: 4
Start Page Number: 786
End Page Number: 794
Publication Date: Nov 2010
Journal: Mathematics of Operations Research
Authors: , , ,
Keywords: polyhedra
Abstract:

We investigate the diameter of a natural abstraction of the 1-skeleton of polyhedra. Even if this abstraction is more general than other abstractions previously studied in the literature, known upper bounds on the diameter of polyhedra continue to hold here. On the other hand, we show that this abstraction has its limits by providing an almost quadratic lower bound.

Reviews

Required fields are marked *. Your email address will not be published.