A polynomial time approximation scheme for the minimum maximal matching problem in planar graphs (New Developments of Theory of Computation and Algorithms)
Hiroshi Nagamochi, Yukihiro Nishida, Toshihide Ibaraki · Kyoto University Research Information Repository (Kyoto University) · 2001
Given an undirected graph $G$ , the minimum maximal matching problem asks to find aminimum matching that is inclusionwise maximal.The problem is known to be NPhard even if the graph is planar.We consider the problem for planar graphs, and show that apolynomial time approximation scheme (PTAS) can be obtained by adivide-and-conquer method based on the planar separator theorem.For agiven $\epsilon>0$ , our scheme delivers in $O(n\log nf\alpha e\epsilon^{-1}n)\star$ time asolution with size at most $(1+\epsilon)$ times the optimal value, where $n$ is the number of vertices in $G$ and $\alpha$ is aconstant number.