Go backward to 34 HomologyGo up to 7 Beyond PolytopesGo 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 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? |