Approximation algorithms for Max Morse matching (Q2362103): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Krzysztof Gdawiec / rank | |||
Property / reviewed by | |||
Property / reviewed by: Krzysztof Gdawiec / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: Simplicial complex library / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2340262195 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1604.04707 / rank | |||
Normal rank |
Revision as of 05:56, 19 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximation algorithms for Max Morse matching |
scientific article |
Statements
Approximation algorithms for Max Morse matching (English)
0 references
5 July 2017
0 references
The authors deal with the Max Morse matching problem (MMMP). In the problem we have a Hasse graph \(H_K\) of a simplicial complex \(K\) whose edges are all directed from a simplex to its lower dimensional facets. We associate a matching induced orientation to \(H_K\) such that the resulting oriented graph is acyclic. The goal in the MMMP is to maximize the cardinality of matched (regular) nodes. In the paper the authors describe a \((D+1) / (D^2 + D +1)\)-factor approximation algorithm for the MMMP on \(D\)-dimensional simplicial complexes. The algorithm uses maximum-cardinality bipartite matching on the Hasse graph to orient it. Then it uses a BFS-like traversal of the oriented Hasse graph to classify matching edges as either forward or backward edges. To prove the approximation bound that holds for manifold and non-manifold complexes a counting argument is used. Next, the authors propose two approximation algorithms for simplicial \(D\)-manifolds. The first approximation algorithm provides a ratio of \(2 / (D+1)\) for \(D \geq 3\) and next the ratio is improved to \(2 / D\) for \(D \geq 5\) using a refinement that specifies the order in which the graph is processed. This leads to \(1/2\)- and \(4/9\)-factor approximation for \(3\)- and \(4\)-manifolds, respectively. To show the effectiveness of the proposed algorithms the authors compare the Java implementation of these algorithms with three other algorithms.
0 references
discrete Morse theory
0 references
approximation algorithms
0 references
computational topology
0 references
Max Morse matching problem
0 references
Hasse graph
0 references
simplicial complex
0 references
algorithm
0 references
simplicial \(D\)-manifolds
0 references