Approximability of the Minimum Maximal Matching Problem in Planar Graphs

Hiroshi NAGAMOCHI; Yukihiro NISHIDA; Toshihide IBARAKI

Approximability of the Minimum Maximal Matching Problem in Planar Graphs

Hiroshi NAGAMOCHI, Yukihiro NISHIDA, Toshihide IBARAKI

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.12 pp.3251-3258

Publication Date: 2003/12/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Graphs and Networks

Cite this

Copy

Hiroshi NAGAMOCHI, Yukihiro NISHIDA, Toshihide IBARAKI, "Approximability of the Minimum Maximal Matching Problem in Planar Graphs" in IEICE TRANSACTIONS on Fundamentals, vol. E86-A, no. 12, pp. 3251-3258, December 2003, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e86-a_12_3251/_p

Copy

@ARTICLE{e86-a_12_3251,
author={Hiroshi NAGAMOCHI, Yukihiro NISHIDA, Toshihide IBARAKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Approximability of the Minimum Maximal Matching Problem in Planar Graphs},
year={2003},
volume={E86-A},
number={12},
pages={3251-3258},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Approximability of the Minimum Maximal Matching Problem in Planar Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 3251
EP - 3258
AU - Hiroshi NAGAMOCHI
AU - Yukihiro NISHIDA
AU - Toshihide IBARAKI
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2003
AB - 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.
ER -