Recognizing shrinkable complexes is NP-complete

DOI10.20382/JOCG.V7I1A18MaRDI QIDQ2970458zbMATH OpenFDO

Authors Olivier Devillers, Marc Glisse, Sylvain Lazard, D. Attali

Publication date 30 March 2017

Full work available at URL https://doi.org/10.20382/JOCG.V7I1A18

Mathematics Subject Classification ID

General topology of complexes (57Q05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Recognizing shrinkable complexes is NP-complete
• Recognition of collapsible complexes is NP-complete
• Shellability is NP-complete
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• Shellability is NP-complete

Cited in

(11)

• Recognising a partitionable simplicial complex is in \(\text{NP}\)
• Multigraded minimal free resolutions of simplicial subclutters
• Recognizing shrinkable complexes is NP-complete
• Variable Dimension Complexes Part I: Basic Theory
• The Shrinking Property for NP and coNP
• Shellability is NP-complete
• Shellability is NP-complete
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• Vertex decompositions of two-dimensional complexes and graphs
• Completions and ramifications
• The shrinking property for NP and coNP

This page was built for publication: Recognizing shrinkable complexes is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970458)