2004/08/24 by Michael Joswig, Joswig, Michael, Marc E. Pfetsch +1 · 1 citation
Computer Science · Mathematics · #52B99 #57Q05 #57R70) #90C27 (06A07 #Algorithms and Data Compression #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Optimization and Control (math.OC) #Topological and Geometric Data Analysis #math.CO #math.OC #msc:52B99 #msc:57Q05 #msc:90C27
paper · pdf · doi:10.48550/arxiv.math/0408331
arxiv created 2004/08/24 · openalex publication_date 2004/08/24 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.