Input: | Finite abstract pure simplicial complex D given by a
list of facets |
---|---|

Output: | "Yes" if D is shellable, "No" otherwise |

Status (general): | Open |
---|---|

Status (fixed dim.): | Open |

Given an ordering of the facets of D, 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 For two-dimensional pseudo-manifolds the problem can be solved in linear time (Danarj and Klee [13]). |

Related problems: | 18, 36 |
---|