Go backward to 9 Recognizing Integer Polyhedra
Go up to 2 Coordinate Descriptions
Go forward to 11 Minimum Triangulation
|
Go backward to 9 Recognizing Integer Polyhedra Go up to 2 Coordinate Descriptions Go forward to 11 Minimum Triangulation |
XHTML 1.0 |
| Input: | Polytope P in H-description |
|---|---|
| Output: | The diameter of P |
| Status (general): | NP -hard |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
Frieze and Teng [21] gave the proof of NP-hardness. For
fixed dimension, one can enumerate all vertices
(Problem 1), construct the graph and
then compute the diameter in polynomial time.
The complexity status is unknown for simple polytopes. For simplicial polytopes the problem can be solved in polynomial time: Since simplicial polytopes have at most as many vertices as facets, one can enumerate their vertices (see Problem 1), and finally compute the graph (and hence the diameter) from the vertex-facet incidences in polynomial time. If P is given in V-description, one can compute the graph (1-skeleton, see Problem 5) and hence the diameter in polynomial time. |
|
|
Why are some symbols not displayed correctly? |