Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete

DOI10.1007/978-3-540-79126-3_17zbMath1138.68604OpenAlexW1556856743MaRDI QIDQ5458885

A. R. Francés, Rémy Malgouyres

Publication date: 24 April 2008

Published in: Discrete Geometry for Computer Imagery (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79126-3_17

zbMATH Keywords

NP-completenessComputational ComplexityCollapsingSimplicial Topology

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

NP-Hardness of Computing PL Geometric Category in Dimension 2 ⋮ Morphological hierarchies: a unifying framework with new trees ⋮ A topological tree of shapes ⋮ Collapsibility to a subcomplex of a given dimension is NP-complete ⋮ Powerful parallel and symmetric 3D thinning schemes based on critical kernels ⋮ Recognition of collapsible complexes is NP-complete ⋮ Shellings from relative shellings, with an application to NP-completeness ⋮ Unnamed Item ⋮ Parameterized Complexity of Discrete Morse Theory ⋮ d-collapsibility is NP-complete for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mi>d</mml:mi><mml:mo>⩾</mml:mo><mml:mn>4</mml:mn></mml:math> ⋮ Searching combinatorial optimality using graph-based homology information

Cites Work

• A concise characterization of 3D simple points
• A computationally intractable problem on simplicial complexes
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete