Recognizing shrinkable complexes is NP-complete
Abstract
We say that a simplicial complex is shrinkable if there exists a sequence of admissible edge contractions that reduces the complex to a single vertex. We prove that it is NP-complete to decide whether a (three-dimensional) simplicial complex is shrinkable. Along the way, we describe examples of contractible complexes which are not shrinkable.
Domains
Computational Geometry [cs.CG]
Fichier principal
esa.pdf (1.36 Mo)
Télécharger le fichier
show.jpg (1.05 Mo)
Télécharger le fichier
| Origin | Files produced by the author(s) |
|---|
| Format | Figure, Image |
|---|
Loading...