On the approximability of the maximum induced matching problem
type: Item
instance of: scholarly article
title: On the approximability of the maximum induced matching problem
zbMATH Open document ID: 1075.68063
author: W. Duckworth
author: David F. Manlove
author: Michele Zito
published in: Journal of Discrete Algorithms
publication date: 2005-05-04T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 2165395
zbMATH Keywords: Induced matching
zbMATH Keywords: Strong matching
zbMATH Keywords: Regular graph
zbMATH Keywords: Approximation algorithm
zbMATH Keywords: APX-completeness
MaRDI profile type: Publication
full work available at URL: j.jda.2004.05.001
OpenAlex ID: W2015698277
cites work: Some APX-completeness results for cubic graphs
cites work: Q4258216
cites work: Q4187840
cites work: Structure and stability number of chair-, co-P- and gem-free graphs revisited
cites work: Induced matchings
cites work: Induced matchings in intersection graphs.
cites work: Finding a maximum induced matching in weakly chordal graphs
cites work: Induced matchings in asteroidal triple-free graphs
cites work: Fundamentals of Computation Theory
cites work: A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
cites work: Q3139292
cites work: Q4198056
cites work: Irredundancy in circular arc graphs
cites work: New results on induced matchings
cites work: Q4368728
cites work: Bipartite Domination and Simultaneous Matroid Covers
cites work: Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
cites work: Some results on graphs without long induced paths
cites work: On maximum induced matchings in bipartite graphs
cites work: The strong chromatic index ofC4-free graphs
cites work: On the computational complexity of strong edge coloring
cites work: Optimization, approximation, and complexity classes
cites work: A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
cites work: NP-completeness of some generalizations of the maximum matching problem
cites work: Q4944970
DOI: 10.1016/J.JDA.2004.05.001
Recommended article: Approximability results for the maximum and minimum maximal induced matching problems
Recommended article: Moderately exponential time algorithms for the maximum induced matching problem
Recommended article: Q3161275
Recommended article: On the induced matching problem
Recommended article: On the Induced Matching Problem
Recommended article: An Improved Exact Algorithm for Maximum Induced Matching
Recommended article: The parameterized complexity of the induced matching problem
Recommended article: Exact algorithms for maximum induced matching
Recommended article: Approximation and Online Algorithms
Recommended article: Maximum induced matchings close to maximum matchings
description: scientific article; zbMATH DE number 2165395