Change search
ReferencesLink to record
Permanent link

Direct link
Recognition of Collapsible Complexes is NP-Complete
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.). Department of Applied Mathematics, Charles University in Prague, Czech Republic.
2016 (English)In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 55, no 1, 21-38 p.Article in journal (Refereed) PublishedText
Abstract [en]

We prove that it is NP-complete to decide whether a given (3-dimensional) simplicial complex is collapsible. This work extends a result of Malgouyres and Francés showing that it is NP-complete to decide whether a given simplicial complex collapses to a 1-complex.

Place, publisher, year, edition, pages
Springer-Verlag New York, 2016. Vol. 55, no 1, 21-38 p.
Keyword [en]
Bing’s house, Collapsibility, NP-hardness, Simplicial complex
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-181450DOI: 10.1007/s00454-015-9747-1ScopusID: 2-s2.0-84953348258OAI: oai:DiVA.org:kth-181450DiVA: diva2:900181
Note

QC 20160203

Available from: 2016-02-03 Created: 2016-02-02 Last updated: 2016-02-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Tancer, Martin
By organisation
Mathematics (Dept.)
In the same journal
Discrete & Computational Geometry
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 13 hits
ReferencesLink to record
Permanent link

Direct link