Computing Optimal Morse Matchings
From MaRDI portal
Abstract: 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.
Recommendations
- Approximation algorithms for Max Morse matching
- Computing Optimal Discrete Morse Functions
- Hardness of approximation for Morse matching
- Morse matchings on polytopes
- Toward Optimality in Discrete Morse Theory
- On optimizing discrete Morse functions
- On computing an optimal semi-matching
- On computing an optimal semi-matching
- Optimal solutions to pattern matching problems
- Optimal matchings in posets
Cited in
(41)- The number of critical elements of discrete Morse functions on non-compact surfaces
- An entropy-based persistence barcode
- Collapsibility to a subcomplex of a given dimension is NP-complete
- Morse matchings on polytopes
- Frontiers of sphere recognition in practice
- On the local homology of Artin groups of finite and affine type
- Searching combinatorial optimality using graph-based homology information
- Extremal examples of collapsible complexes and random discrete Morse theory
- Approximation algorithms for Max Morse matching
- Allowing cycles in discrete Morse theory
- A graph-theoretical approach to cancelling critical elements
- Discrete Morse theory for manifolds with boundary
- Computing Optimal Discrete Morse Functions
- Notes on the simplification of the Morse-Smale complex
- Courcelle's theorem for triangulations
- Morse theory for filtrations and efficient computation of persistent homology
- Discrete Morse theory for the moduli spaces of polygonal linkages, or solitaire on a circle
- Shellability is NP-complete
- On the rooted forests in triangulated closed manifolds
- Hardness of approximation for Morse matching
- Random discrete Morse theory and a new library of triangulations
- Recognition of collapsible complexes is NP-complete
- Generalised cone complexes and tropical moduli in polymake
- Discrete Morse theory for computing zigzag persistence
- Shellable tilings on relative simplicial complexes and their h-vectors
- On discrete gradient vector fields and Laplacians of simplicial complexes
- Optimal topological simplification of discrete functions on surfaces
- From finite vector field data to combinatorial dynamical systems in the sense of Forman
- Multivariate central limit theorems for random clique complexes
- Morse theoretic signal compression and reconstruction on chain complexes
- Analyzing multifiltering functions using multiparameter discrete Morse theory
- Perfect matching complexes of polygonal line tilings
- Morse sequences: a simple approach to discrete Morse theory
- Topology of matching complexes of complete graphs via discrete Morse theory
- Parameterized inapproximability of Morse matching
- Goodness-of-fit via count statistics in dense random simplicial complexes
- Discrete Morse theory for open complexes
- Morse sequences on stacks and flooding sequences
- SCIP: solving constraint integer programs
- Birth and death in discrete Morse theory
- Reducing complexes in multidimensional persistent homology theory
This page was built for publication: Computing Optimal Morse Matchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470812)
