Back to Search
Start Over
Approximation algorithms for Max Morse Matching.
- Source :
-
Computational Geometry . Feb2017, Vol. 61, p1-23. 23p. - Publication Year :
- 2017
-
Abstract
- In this paper, we prove that the Max Morse Matching Problem is approximable, thus resolving an open problem posed by Joswig and Pfetsch [1] . For D -dimensional simplicial complexes, we obtain a ( D + 1 ) ( D 2 + D + 1 ) -factor approximation ratio using a simple edge reorientation algorithm that removes cycles. For D ≥ 5 , we describe a 2 D -factor approximation algorithm for simplicial manifolds by processing the simplices in increasing order of dimension. This algorithm leads to 1 2 -factor approximation for 3-manifolds and 4 9 -factor approximation for 4-manifolds. This algorithm may also be applied to non-manifolds resulting in a 1 ( D + 1 ) -factor approximation ratio. One application of these algorithms is towards efficient homology computation of simplicial complexes. Experiments using a prototype implementation on several datasets indicate that the algorithm computes near optimal results. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09257721
- Volume :
- 61
- Database :
- Academic Search Index
- Journal :
- Computational Geometry
- Publication Type :
- Academic Journal
- Accession number :
- 120225481
- Full Text :
- https://doi.org/10.1016/j.comgeo.2016.10.002