On the approximability of the maximum induced matching problem
From MaRDI portal
Publication:1775017
DOI10.1016/j.jda.2004.05.001zbMath1075.68063MaRDI QIDQ1775017
David F. Manlove, Michele Zito, William Duckworth
Publication date: 4 May 2005
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2004.05.001
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Improved induced matchings in sparse graphs, On the induced matching problem, Maximum regular induced subgraphs in \(2P_3\)-free graphs, On distance-3 matchings and induced matchings, Approximability results for the maximum and minimum maximal induced matching problems, Approximation hardness of dominating set problems in bounded degree graphs, Efficient edge domination in regular graphs, The parameterized complexity of the induced matching problem, An inequality for polymatroid functions and its applications., Maximum induced matchings of random cubic graphs, The complexity of dissociation set problems in graphs, Generalizing the induced matching by edge capacity constraints, On Distance-3 Matchings and Induced Matchings, Improved Induced Matchings in Sparse Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Irredundancy in circular arc graphs
- A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
- Structure and stability number of chair-, co-P- and gem-free graphs revisited
- Some results on graphs without long induced paths
- NP-completeness of some generalizations of the maximum matching problem
- Optimization, approximation, and complexity classes
- Induced matchings
- Induced matchings in asteroidal triple-free graphs
- Induced matchings in intersection graphs.
- Some APX-completeness results for cubic graphs
- On the computational complexity of strong edge coloring
- 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
- Finding a maximum induced matching in weakly chordal graphs
- On maximum induced matchings in bipartite graphs
- A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
- New results on induced matchings
- Bipartite Domination and Simultaneous Matroid Covers
- Fundamentals of Computation Theory
