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.
Domaines
Géométrie algorithmique [cs.CG]
Fichier principal
275-1183-1-PB.pdf (4.38 Mo)
Télécharger le 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 produits par l'(les) auteur(s)
Origine : Fichiers éditeurs autorisés sur une archive ouverte