Approximability results for the maximum and minimum maximal induced matching problems
From MaRDI portal
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
- scientific article; zbMATH DE number 5799830
- On the approximability of the maximum induced matching problem
- On maximum induced matchings in bipartite graphs
- Publication:4944970
- 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
- scientific article; zbMATH DE number 434499 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (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 3252052 (Why is no real title available?)
- Algorithms – ESA 2004
- Approximation and Online Algorithms
- Bipartite Domination and Simultaneous Matroid Covers
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- 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
- Graph Classes: A Survey
- Graph theory with applications
- Independent Sets in Asteroidal Triple-Free Graphs
- Independent domination in chordal graphs
- Induced matchings
- Induced matchings in asteroidal triple-free graphs
- Induced matchings in intersection graphs.
- Irredundancy in circular arc graphs
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Maximum induced matchings in graphs
- NP-completeness of some generalizations of the maximum matching problem
- New results on induced matchings
- On induced matchings
- On the Complexity of General Graph Factor Problems
- On the approximability of the maximum induced matching problem
- On the completeness of a generalized matching problem
- Planar 3DM is NP-complete
- Problems and results in combinatorial analysis and graph theory
- The P k Partition Problem and Related Problems in Bipartite Graphs
- The complexity of theorem-proving procedures
Cited in
(31)- Minimum maximal acyclic matching in proper interval graphs
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
- scientific article; zbMATH DE number 5799830 (Why is no real title available?)
- Approximating weighted induced matchings
- Almost induced matching: linear kernels and parameterized algorithms
- The complexity of dissociation set problems in graphs
- Hardness and approximation of minimum maximal matchings
- Approximating maximum acyclic matchings by greedy and local search strategies
- On the computational complexity of the Helly number in the \(P_3\) and related convexities
- Parameterized algorithms and kernels for almost induced matching
- Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier
- Exact algorithms for maximum induced matching
- A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
- On the complexity of minimum maximal acyclic matchings
- Graphs with maximal induced matchings of the same size
- A Min-Max Theorem for a Constrained Matching Problem
- The parameterized complexity of the induced matching problem
- Moderately exponential time algorithms for the maximum induced matching problem
- Minimum maximal acyclic matching in proper interval graphs
- On distance-3 matchings and induced matchings
- New kernels for several problems on planar graphs
- Edge open packing: complexity, algorithmic aspects, and bounds
- On distance-3 matchings and induced matchings
- Weighted upper domination number
- Well-indumatched pseudoforests
- On minimum maximal distance-\(k\) matchings
- On the approximability of the maximum induced matching problem
- On the induced matching problem in Hamiltonian bipartite graphs
- On the complexity of minimum maximal acyclic matchings
- Well-indumatched Trees and Graphs of Bounded Girth
This page was built for publication: Approximability results for the maximum and minimum maximal induced matching problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q937401)
