Recognizing shrinkable complexes is NP-complete - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

Recognizing shrinkable complexes is NP-complete

Olivier Devillers
Marc Glisse

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 (three-dimensional) simplicial complex is shrinkable. Along the way, we describe examples of contractible complexes which are not shrinkable.
Fichier principal
Vignette du fichier
esa.pdf (1.36 Mo) Télécharger le fichier
Vignette du fichier
show.jpg (1.05 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...

Dates et versions

hal-01015747 , version 1 (27-06-2014)

Identifiants

Citer

Dominique Attali, Olivier Devillers, Marc Glisse, Sylvain Lazard. Recognizing shrinkable complexes is NP-complete. ESA 2014 - 22nd Annual European Symposium on Algorithms, Sep 2014, Wroclaw, Poland. pp.74-86, ⟨10.1007/978-3-662-44777-2_7⟩. ⟨hal-01015747⟩
772 Consultations
554 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More