On the approximability of the maximum induced matching problem
From MaRDI portal
Recommendations
- Approximability results for the maximum and minimum maximal induced matching problems
- Moderately exponential time algorithms for the maximum induced matching problem
- scientific article; zbMATH DE number 5799830
- On the induced matching problem
- On the Induced Matching Problem
- An improved exact algorithm for maximum induced matching
- The parameterized complexity of the induced matching problem
- Exact algorithms for maximum induced matching
- Approximation and Online Algorithms
- Maximum induced matchings close to maximum matchings
Cites work
- scientific article; zbMATH DE number 434499 (Why is no real title available?)
- scientific article; zbMATH DE number 3625415 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1420901 (Why is no real title available?)
- A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
- A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
- Bipartite Domination and Simultaneous Matroid Covers
- Finding a maximum induced matching in weakly chordal graphs
- 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
- Inapproximability results for bounded variants of optimization problems.
- Induced matchings
- Induced matchings in asteroidal triple-free graphs
- Induced matchings in intersection graphs.
- Irredundancy in circular arc graphs
- NP-completeness of some generalizations of the maximum matching problem
- New results on induced matchings
- On maximum induced matchings in bipartite graphs
- On the computational complexity of strong edge coloring
- Optimization, approximation, and complexity classes
- Some APX-completeness results for cubic graphs
- Some results on graphs without long induced paths
- Structure and stability number of chair-, co-P- and gem-free graphs revisited
- The strong chromatic index ofC4-free graphs
Cited in
(53)- Maximum matching in multi-interface networks
- Strong edge-colouring and induced matchings
- Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
- Improved induced matchings in sparse graphs
- On the induced matching problem
- Induced Matching in Some Subclasses of Bipartite Graphs
- scientific article; zbMATH DE number 5799830 (Why is no real title available?)
- Maximum regular induced subgraphs in 2P₃-free graphs
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- A bisection approach to subcubic maximum induced matching
- Approximating weighted induced matchings
- Almost induced matching: linear kernels and parameterized algorithms
- A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
- Maximum induced matchings of random cubic graphs
- The complexity of dissociation set problems in graphs
- Approximating maximum acyclic matchings by greedy and local search strategies
- Maximum induced matching of hexagonal graphs
- Parameterized algorithms and kernels for almost induced matching
- On the Induced Matching Problem
- Maximum induced matching problem on hhd-free graphs
- Induced matchings in graphs of degree at most 4
- A \(\frac{1}{2}\)-integral relaxation for the \(A\)-matching problem
- Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier
- Approximation and Online Algorithms
- On some hard and some tractable cases of the maximum acyclic matching problem
- Exact algorithms for maximum induced matching
- MIP formulations for induced graph optimization problems: a tutorial
- Maximum weight induced matching in some subclasses of bipartite graphs
- Improved induced matchings in sparse graphs
- An inequality for polymatroid functions and its applications.
- A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
- Generalizing the induced matching by edge capacity constraints
- scientific article; zbMATH DE number 1420901 (Why is no real title available?)
- A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem
- Efficient edge domination in regular graphs
- The parameterized complexity of the induced matching problem
- Moderately exponential time algorithms for the maximum induced matching problem
- On distance-3 matchings and induced matchings
- Approximation hardness of dominating set problems in bounded degree graphs
- An improved kernel and parameterized algorithm for almost induced matching
- New kernels for several problems on planar graphs
- Maximum induced matching algorithms via vertex ordering characterizations
- On distance-3 matchings and induced matchings
- Maximum induced matching algorithms via vertex ordering characterizations
- Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
- Well-indumatched pseudoforests
- Approximability results for the maximum and minimum maximal induced matching problems
- Two greedy consequences for maximum induced matchings
- Recent progress on strong edge-coloring of graphs
- Locally searching for large induced matchings
- On the induced matching problem in Hamiltonian bipartite graphs
- On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs
- Well-indumatched Trees and Graphs of Bounded Girth
This page was built for publication: On the approximability of the maximum induced matching problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1775017)
