On the approximability of the maximum induced matching problem

William Duckworth; David F. Manlove; Michele Zito

doi:10.1016/j.jda.2004.05.001

On the approximability of the maximum induced matching problem

William Duckworth, David F. Manlove, Michele Zito

School of Computing

Research output: Contribution to journal › Article › peer-review

74 Citations (Scopus)

Abstract

In this paper we consider the approximability of the maximum induced matching problem (MIM). We give an approximation algorithm with asymptotic performance ratio d − 1 for MIM in d-regular graphs, for each d ≥3. We also prove that MIM is APX-complete in d-regular graphs, for each d ≥3.

Original language	English
Pages (from-to)	79-91
Number of pages	13
Journal	Journal of Discrete Algorithms (Amsterdam)
Volume	3
Issue number	1
DOIs	https://doi.org/10.1016/j.jda.2004.05.001
Publication status	Published - 2005

Access to Document

10.1016/j.jda.2004.05.001

Cite this

@article{5e6671f438bf43a8b751ef7a169e211f,

title = "On the approximability of the maximum induced matching problem",

abstract = "In this paper we consider the approximability of the maximum induced matching problem (MIM). We give an approximation algorithm with asymptotic performance ratio d − 1 for MIM in d-regular graphs, for each d ≥3. We also prove that MIM is APX-complete in d-regular graphs, for each d ≥3.",

author = "William Duckworth and Manlove, {David F.} and Michele Zito",

year = "2005",

doi = "10.1016/j.jda.2004.05.001",

language = "English",

volume = "3",

pages = "79--91",

journal = "Journal of Discrete Algorithms (Amsterdam)",

issn = "1570-8667",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - On the approximability of the maximum induced matching problem

AU - Duckworth, William

AU - Manlove, David F.

AU - Zito, Michele

PY - 2005

Y1 - 2005

N2 - In this paper we consider the approximability of the maximum induced matching problem (MIM). We give an approximation algorithm with asymptotic performance ratio d − 1 for MIM in d-regular graphs, for each d ≥3. We also prove that MIM is APX-complete in d-regular graphs, for each d ≥3.

AB - In this paper we consider the approximability of the maximum induced matching problem (MIM). We give an approximation algorithm with asymptotic performance ratio d − 1 for MIM in d-regular graphs, for each d ≥3. We also prove that MIM is APX-complete in d-regular graphs, for each d ≥3.

U2 - 10.1016/j.jda.2004.05.001

DO - 10.1016/j.jda.2004.05.001

M3 - Article

SN - 1570-8667

VL - 3

SP - 79

EP - 91

JO - Journal of Discrete Algorithms (Amsterdam)

JF - Journal of Discrete Algorithms (Amsterdam)

IS - 1

ER -

On the approximability of the maximum induced matching problem

Abstract

Access to Document

Fingerprint

Cite this