Recognizing Shrinkable Complexes Is NP-Complete

Dominique Attali 1 Olivier Devillers 2 Marc Glisse 3 Sylvain Lazard 2
1 GIPSA-AGPIG - AGPIG
GIPSA-DIS - Département Images et Signal
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
3 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
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.
Type de document :
Article dans une revue
Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2016, 7 (1), pp.430--443. 〈http://jocg.org/index.php/jocg/article/view/275〉. 〈10.20382/jocg.v7i1a18〉
Liste complète des métadonnées

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


https://hal.inria.fr/hal-01384396
Contributeur : Olivier Devillers <>
Soumis le : lundi 5 mars 2018 - 11:01:46
Dernière modification le : lundi 9 avril 2018 - 12:22:33

Identifiants

Citation

Dominique Attali, Olivier Devillers, Marc Glisse, Sylvain Lazard. Recognizing Shrinkable Complexes Is NP-Complete. Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2016, 7 (1), pp.430--443. 〈http://jocg.org/index.php/jocg/article/view/275〉. 〈10.20382/jocg.v7i1a18〉. 〈hal-01384396v2〉

Partager

Métriques

Consultations de la notice

324

Téléchargements de fichiers

66