Go up to 3 Combinatorial Structure
Go forward to 15 f-Vector of Combinatorial Polytopes
|
Go up to 3 Combinatorial Structure Go forward to 15 f-Vector of Combinatorial Polytopes |
XHTML 1.0 |
| Input: | Vertex-facet incidence matrix of a polytope P |
|---|---|
| Output: | Hasse-diagram of the face lattice of P |
| Status (general): | Polynomial total time |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
Solvable in O(min{m,n}· α· φ) time,
where m is the number of facets, n is the number of vertices,
α is the number of vertex-facet incidences, and φ
is the size of the face lattice [33]. Note that φ
is exponential in d (for fixed d it is polynomial in m
and n). Without (asymptotically) increasing the running time it
is also possible to label each node in the Hasse diagram by the
dimension and the vertex set of the corresponding face.
It follows from [33] that one can compute the Hasse-diagram of the k-skeleton (i.e., all faces of dimensions at most k) of P in O(n· α· φ≤k) time, where φ≤k is the number of faces of dimensions at most k. Since the latter number is in O(nk+1), the k-skeleton can be computed in polynomial time (in the input size) for fixed k. |
| Related problems: | 5, 15 |
|---|
|
|
Why are some symbols not displayed correctly? |