Shellability is NP-complete
From MaRDI portal
Publication:5115809
DOI10.4230/LIPICS.SOCG.2018.41zbMATH Open1489.68331MaRDI QIDQ5115809FDOQ5115809
Authors: Xavier Goaoc, Pavel Paták, Zuzana Safernova, Martin Tancer, Uli Wagner 
Publication date: 18 August 2020
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topology of complexes (57Q05) Combinatorial aspects of simplicial complexes (05E45) Computational aspects of digital topology (68U03)
Cites Work
- Combinatorics and commutative algebra.
- Computational Complexity
- Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
- Shellable nonpure complexes and posets. II
- Title not available (Why is that?)
- Convex Polytopes
- The maximum numbers of faces of a convex polytope
- Title not available (Why is that?)
- On Lexicographically Shellable Posets
- Shellable and Cohen-Macaulay Partially Ordered Sets
- Poset topology: tools and applications
- Shellable Decompositions of Cells and Spheres.
- Bruhat order of Coxeter groups and shellability
- Title not available (Why is that?)
- Computing Optimal Morse Matchings
- Shellings of spheres and polytopes
- How to shell a monoid
- THE PROBLEM OF DISCRIMINATING ALGORITHMICALLY THE STANDARD THREE-DIMENSIONAL SPHERE
- On the shellability of the order complex of the subgroup lattice of a finite group
- Optimal discrete Morse functions for 2-manifolds
- Decompositions of two-dimensional simplicial complexes
- Title not available (Why is that?)
- Which Spheres are Shellable?
- Einstein structures: Existence versus uniqueness
- A computationally intractable problem on simplicial complexes
- Title not available (Why is that?)
- Recognition of collapsible complexes is NP-complete
- A Representation of 2-dimensional Pseudomanifolds and its use in the Design of a Linear-Time Shelling Algorithm
- Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
- Title not available (Why is that?)
Cited In (9)
- Title not available (Why is that?)
- \(h\)-assignments of simplicial complexes and reverse search
- Hyperplane Neural Codes and the Polar Complex
- \(D\)-collapsibility is NP-complete for \(d \geq 4\)
- LaserTank is NP-Complete
- Decomposable clutters and a generalization of Simon's conjecture
- Shellings from relative shellings, with an application to NP-completeness
- Counting shellings of complete bipartite graphs and trees
- Title not available (Why is that?)
This page was built for publication: Shellability is NP-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115809)
