Return to Colloquia & Seminar listing
Computing optimal discrete Morse functions
Algebra & 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)).