d-collapsibility is NP-complete for d greater or equal to 4
From MaRDI portal
Publication:5414577
DOI10.4086/cjtcs.2010.003zbMath1286.68210arXiv0808.1991OpenAlexW4254521354MaRDI QIDQ5414577
Publication date: 6 May 2014
Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0808.1991
Related Items
Extensions of the colorful Helly theorem for d-collapsible and d-Leray complexes ⋮ Planar Convex Codes are Decidable ⋮ Tight complexes in 3-space admit perfect discrete Morse functions ⋮ A counterexample to Wegner's conjecture on good covers ⋮ Recognition of collapsible complexes is NP-complete ⋮ Chordality, \(d\)-collapsibility, and componentwise linear ideals
This page was built for publication: d-collapsibility is NP-complete for d greater or equal to 4