Recognizing shrinkable complexes is NP-complete

Dominique Attali 1 Olivier Devillers 2 Marc Glisse 2 Sylvain Lazard 3
1 GIPSA-AGPIG - AGPIG
GIPSA-DIS - Département Images et Signal
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
3 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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.
Type de document :
Communication dans un congrès
A. Schulz and D. Wagner. 22nd European Symposium on Algorithms, 2014, Wroclaw, Poland. Springer, 8737, pp.74-86, 2014
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-01015747
Contributeur : Olivier Devillers <>
Soumis le : vendredi 27 juin 2014 - 09:45:30
Dernière modification le : samedi 2 décembre 2017 - 01:28:42
Document(s) archivé(s) le : samedi 27 septembre 2014 - 10:50:38

Fichiers

esa.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01015747, version 1

Citation

Dominique Attali, Olivier Devillers, Marc Glisse, Sylvain Lazard. Recognizing shrinkable complexes is NP-complete. A. Schulz and D. Wagner. 22nd European Symposium on Algorithms, 2014, Wroclaw, Poland. Springer, 8737, pp.74-86, 2014. 〈hal-01015747〉

Partager

Métriques

Consultations de la notice

592

Téléchargements de fichiers

406