For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Approximability of the Minimum Maximal Matching Problem in Planar Graphs
Hiroshi NAGAMOCHI Yukihiro NISHIDA Toshihide IBARAKI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/12/01
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
graph algorithm, approximation algorithm, matching, planar graph, separator,
Full Text: PDF(259.3KB)>>
Given an edge-weighted graph G, the minimum maximal matching problem asks to find a minimum weight maximal matching. The problem is known to be NP-hard even if the graph is planar and unweighted. In this paper, we consider the problem in planar graphs. First, we prove a strong inapproximability for the problem in weighted planar graphs. Second, in contrast with the first result, we show that a polynomial time approximation scheme (PTAS) for the problem in unweighted planar graphs can be obtained by a divide-and-conquer method based on the planar separator theorem. For a given ε > 0, our scheme delivers in time a solution with size at most (1 + ε) times the optimal value, where n is the number of vertices in G and α is a constant number.