Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Computing optimal discrete Morse functionsAlgebra & Discrete Mathematics
|Speaker: ||Michael Joswig, TU Darmstadt and MSRI|
|Location: ||1147 MSB|
|Start time: ||Fri, Sep 29 2006, 12:10PM|
Morse matchings capture the essential structural information of discrete Morse functions, as introduced by Forman. We show that computing optimal Morse matchings is NP-hard and give an integer programming formulation for the problem. Then we present polyhedral results for the corresponding polytope and report on computational results. For the purpose of
understanding the talk no knowledge in either classical or discrete Morse theory is assumed.
(Joint work with Marc E. Pfetsch (ZIB Berlin)).