On the approximability of the maximum induced matching problem
From MaRDI portal
Publication:1775017
DOI10.1016/j.jda.2004.05.001zbMath1075.68063OpenAlexW2015698277MaRDI QIDQ1775017
William Duckworth, Michele Zito, David F. Manlove
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
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem ⋮ Exact algorithms for maximum induced matching ⋮ Improved induced matchings in sparse graphs ⋮ Maximum matching in multi-interface networks ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Unnamed Item ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ An inequality for polymatroid functions and its applications. ⋮ Locally searching for large induced matchings ⋮ Induced Matching in Some Subclasses of Bipartite Graphs ⋮ Parameterized algorithms and kernels for almost induced matching ⋮ Strong edge-colouring and induced matchings ⋮ Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem ⋮ Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier ⋮ On the induced matching problem ⋮ Well-indumatched Trees and Graphs of Bounded Girth ⋮ Approximability results for the maximum and minimum maximal induced matching problems ⋮ Two greedy consequences for maximum induced matchings ⋮ Generalizing the induced matching by edge capacity constraints ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ Approximating weighted induced matchings ⋮ Approximation hardness of dominating set problems in bounded degree graphs ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ Induced Matchings in Graphs of Degree at Most 4 ⋮ Approximating maximum acyclic matchings by greedy and local search strategies ⋮ On distance-3 matchings and induced matchings ⋮ Maximum weight induced matching in some subclasses of bipartite graphs ⋮ The complexity of dissociation set problems in graphs ⋮ Maximum induced matching of hexagonal graphs ⋮ On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs ⋮ New kernels for several problems on planar graphs ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Efficient edge domination in regular graphs ⋮ On the induced matching problem in Hamiltonian bipartite graphs ⋮ The parameterized complexity of the induced matching problem ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Improved Induced Matchings in Sparse Graphs ⋮ Recent progress on strong edge-coloring of graphs ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Moderately exponential time algorithms for the maximum induced matching problem ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs ⋮ Maximum induced matchings of random cubic graphs
Cites Work
- 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
- The strong chromatic index ofC4-free graphs
- Fundamentals of Computation Theory
