Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.