Recognizing Shrinkable Complexes Is NP-Complete - Archive ouverte HAL Access content directly
Journal Articles Journal of Computational Geometry Year : 2016

Recognizing Shrinkable Complexes Is NP-Complete

(1) , (2) , (3) , (2)
1
2
3

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.

Domains

Computer Science [cs] Computational Geometry [cs.CG]
Fichier principal
Vignette du fichier
jocg.pdf (4.29 Mo) Télécharger le fichier
Vignette du fichier
vignette.jpg (1.05 Mo) Télécharger le fichier
Vignette du fichier
supplementary-material.pdf (9.83 Mo) Télécharger le fichier
Vignette du fichier
vignette.pdf (1.05 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image

Olivier Devillers  : Connect in order to contact the contributor

https://hal.inria.fr/hal-01384396

Submitted on : Monday, March 5, 2018-11:01:46 AM

Last modification on : Tuesday, August 2, 2022-4:24:52 AM

Download

Dates and versions

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

Identifiers

Cite

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-01384396v2⟩

Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

Collections

UGA CNRS INRIA IRISA GIPSA GIPSA-DIS GIPSA-AGPIG UNIV-LORRAINE INRIA2 LORIA LORIA-ALGO UR1-MATH-STIC UNIV-PARIS-SACLAY UR1-UFR-ISTIC UNIV-COTEDAZUR ANR UR1-MATH-NUM GS-COMPUTER-SCIENCE
893 View
223 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More