Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 06, 2008, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Martin Tancer (Charles Univ., Prague)
A simplicial complex K is d-collapsible if it can be reduced to an empty complex by repeatedly removing a face of dimension at most d-1 that is contained in a unique maximal face. The motivation for this notion is that the set of d-collapsible complexes is known to be a superset of the set of complexes that are the nerves of collections of convex sets in R^d. We sketch the proof that the problem of recognition of d-collapsible complexes is polynomial for d at most 2, and NP-complete for d greater or equal to 4.
Automatic MiSe System Software Version 1.4803M | admin login