Computing Optimal Morse Matchings
Please always quote using this URN: urn:nbn:de:0297-zib-8120
- Morse matchings capture the essential structural information of discrete Morse functions. 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.
| Author: | Michael Joswig, Marc PfetschORCiD |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | Morse matching; discrete Morse function |
| MSC-Classification: | 06-XX ORDER, LATTICES, ORDERED ALGEBRAIC STRUCTURES [See also 18B35] / 06Axx Ordered sets / 06A07 Combinatorics of partially ordered sets |
| 52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B99 None of the above, but in this section | |
| 57-XX MANIFOLDS AND CELL COMPLEXES (For complex manifolds, see 32Qxx) / 57Qxx PL-topology / 57Q05 General topology of complexes | |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
| Date of first Publication: | 2004/08/23 |
| Series (Serial Number): | ZIB-Report (04-37) |
| ZIB-Reportnumber: | 04-37 |
| Published in: | Appeared in: SIAM J. Discrete Mathematics 20 (2006) 11-25 |

