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>
From MaRDI portal
Publication:2851437
DOI10.1016/j.endm.2009.07.009zbMath1272.05208MaRDI QIDQ2851437
Publication date: 10 October 2013
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.endm.2009.07.009
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05E45: Combinatorial aspects of simplicial complexes
Cites Work
- Unnamed Item
- Unnamed Item
- String graphs. II: Recognizing string graphs is NP-hard
- d-collapsing and nerves of families of convex sets
- Representation of a finite graph by a set of intervals on the real line
- Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler