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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Representation of 2-dimensional Pseudomanifolds and its use in the Design of a Linear-Time Shelling Algorithm
- A computationally intractable problem on simplicial complexes
- Bruhat order of Coxeter groups and shellability
- Combinatorics and commutative algebra.
- Computational Complexity
- Computing Optimal Morse Matchings
- Convex Polytopes
- Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
- Decompositions of two-dimensional simplicial complexes
- Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
- Einstein structures: Existence versus uniqueness
- How to shell a monoid
- On Lexicographically Shellable Posets
- On the shellability of the order complex of the subgroup lattice of a finite group
- Optimal discrete Morse functions for 2-manifolds
- Poset topology: tools and applications
- Recognition of collapsible complexes is NP-complete
- Recognizing shrinkable complexes is NP-complete
- Shellability is NP-complete
- Shellable Decompositions of Cells and Spheres.
- Shellable and Cohen-Macaulay Partially Ordered Sets
- Shellable nonpure complexes and posets. II
- Shellings of spheres and polytopes
- THE PROBLEM OF DISCRIMINATING ALGORITHMICALLY THE STANDARD THREE-DIMENSIONAL SPHERE
- The maximum numbers of faces of a convex polytope
- Which Spheres are Shellable?
Cited In (13)
- Shellability is NP-complete
- \(h\)-assignments of simplicial complexes and reverse search
- Shellability is NP-complete
- 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
- Recognizing shrinkable complexes is NP-complete
- Recognizing shrinkable complexes is NP-complete
- \(d\)-collapsibility is NP-complete for \(d \geq 4\)
- 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)
