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 (two-dimensional) simplicial complex is shrinkable. Along the way, we describe examples of contractible complexes that are not shrinkable.
https://hal.inria.fr/hal-01384396
Contributeur : Olivier Devillers
<>
Soumis le : lundi 5 mars 2018 - 11:01:46
Dernière modification le : mardi 18 décembre 2018 - 16:18:26
