A computationally intractable problem on simplicial complexes

DOI10.1016/0925-7721(95)00015-1zbMath0849.68123OpenAlexW2042847888MaRDI QIDQ1917045

Ömer Eğecioğlu, Teofilo F. Gonzalez

Publication date: 14 July 1996

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(95)00015-1

zbMATH Keywords

simplicial complexalgorithmic complexitycollapsingBetti numbers

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

Approximation algorithms for Max Morse matching ⋮ Collapsibility to a subcomplex of a given dimension is NP-complete ⋮ Optimal discrete Morse functions for 2-manifolds ⋮ Recognition of collapsible complexes is NP-complete ⋮ Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete ⋮ Unnamed Item ⋮ Parameterized Complexity of Discrete Morse Theory ⋮ Computing Optimal Discrete Morse Functions

Cites Work

• A simple LP-free approximation algorithm for the minimum weight vertex cover problem
• Lower bounds on testing membership to a polyhedron by algebraic decision trees
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Wait-free k-set agreement is impossible
• The asynchronous computability theorem for t-resilient tasks
• On the hardness of approximating minimization problems
• Efficient probabilistically checkable proofs and applications to approximations
• Decision tree complexity and Betti numbers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A computationally intractable problem on simplicial complexes