Go backward to 34 Homology
Go up to 7 Beyond Polytopes
Go forward to 36 Partitionability
|
Go backward to 34 Homology Go up to 7 Beyond Polytopes Go forward to 36 Partitionability |
XHTML 1.0 |
| Input: | Finite abstract pure simplicial complex Δ given by a list of facets |
|---|---|
| Output: | "Yes" if Δ is shellable, "No" otherwise |
| Status (general): | Open |
|---|---|
| Status (fixed dim.): | Open |
|
Given an ordering of the facets of Δ, it can be tested in
polynomial time whether it is a shelling order. Hence, the problem
in NP.
The problem can be solved in polynomial time for one-dimensional complexes, i.e., for graphs: a graph is shellable if and only if it is connected. Even for dim(Δ) = 2, the status is open. In particular, it is unclear if the problem can be solved in polynomial time if Δ is given by a list of all simplices. For two-dimensional pseudo-manifolds the problem can be solved in linear time (Danarj and Klee [13]). |
| Related problems: | 18, 36 |
|---|
|
|
Why are some symbols not displayed correctly? |