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 |