On the approximability of the maximum induced matching problem

William Duckworth, David F. Manlove, Michele Zito

Research output: Contribution to journalArticle

61 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 languageEnglish
Pages (from-to)79-91
Number of pages13
JournalJournal of Discrete Algorithms (Amsterdam)
Volume3
Issue number1
DOIs
Publication statusPublished - 2005

Fingerprint Dive into the research topics of 'On the approximability of the maximum induced matching problem'. Together they form a unique fingerprint.

Cite this