50 citations · 125 across the 28 of their papers we have counts for
Showing 2008Show all
3 papers · 1 filter
math.CO2008
d-collapsibility is NP-complete for d greater or equal to 4
Martin Tancer
A simplicial complex is d-collapsible if it can be reduced to an empty complex by repeatedly removing (collapsing) a face of dimension at most d-1 that is contained in a unique max…
cs.CG2008★ 18 cited
Hardness of embedding simplicial complexes in
Jiří Matoušek, Martin Tancer, Uli Wagner
Let EMBED(k,d) be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into R^d? Know…
math.CO2008
On the gap between representability and collapsibility
Jiri Matousek, Martin Tancer
A simplicial complex K is called d-representable if it is the nerve of a collection of convex sets in R^d; K is d-collapsible if it can be reduced to an empty complex by repeatedly…