Recognizing Shrinkable Complexes Is NP-Complete - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Computational Geometry Année : 2016

Recognizing Shrinkable Complexes Is NP-Complete

Résumé

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.
Fichier principal
Vignette du fichier
275-1183-1-PB.pdf (4.38 Mo) Télécharger le fichier
Vignette du fichier
vignette.png (71.19 Ko) Télécharger le fichier
275-1185-1-PB.pdf (9.74 Mo) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Format : Figure, Image
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-01384396 , version 1 (19-10-2016)
hal-01384396 , version 2 (05-03-2018)

Identifiants

Citer

Dominique Attali, Olivier Devillers, Marc Glisse, Sylvain Lazard. Recognizing Shrinkable Complexes Is NP-Complete. Journal of Computational Geometry, 2016, 7 (1), pp.430--443. ⟨10.20382/jocg.v7i1a18⟩. ⟨hal-01384396v1⟩
914 Consultations
248 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More