Approximability results for the maximum and minimum maximal induced matching problems
DOI10.1016/J.DISOPT.2007.11.010zbMATH Open1140.90479OpenAlexW1985482016MaRDI QIDQ937401FDOQ937401
Authors: Gerd Finke, Yury L. Orlovich, V. S. Gordon, I.È. Zverovich 
Publication date: 15 August 2008
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: http://elib.bsu.by/handle/123456789/7974
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
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)
Cites Work
- Title not available (Why is that?)
- On the Complexity of General Graph Factor Problems
- Graph Classes: A Survey
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Graph theory with applications
- Planar 3DM is NP-complete
- Title not available (Why is that?)
- On the completeness of a generalized matching problem
- The complexity of theorem-proving procedures
- Title not available (Why is that?)
- Induced matchings
- Problems and results in combinatorial analysis and graph theory
- Induced matchings in asteroidal triple-free graphs
- On induced matchings
- NP-completeness of some generalizations of the maximum matching problem
- 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
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Independent Sets in Asteroidal Triple-Free Graphs
- On the approximability of the maximum induced matching problem
- New results on induced matchings
- Induced matchings in intersection graphs.
- Finding a maximum induced matching in weakly chordal graphs
- Bipartite Domination and Simultaneous Matroid Covers
- Independent domination in chordal graphs
- The P k Partition Problem and Related Problems in Bipartite Graphs
- Algorithms – ESA 2004
- Approximation and Online Algorithms
- Irredundancy in circular arc graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Maximum induced matchings in graphs
Cited In (31)
- Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- Title not available (Why is that?)
- 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
- On the computational complexity of the Helly number in the \(P_3\) and related convexities
- Approximating maximum acyclic matchings by greedy and local search strategies
- 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
- A Min-Max Theorem for a Constrained Matching Problem
- Graphs with maximal induced matchings of the same size
- The parameterized complexity of the induced matching problem
- Minimum maximal acyclic matching in proper interval graphs
- Moderately exponential time algorithms for the maximum induced matching problem
- On distance-3 matchings and induced matchings
- Edge open packing: complexity, algorithmic aspects, and bounds
- New kernels for several problems on planar graphs
- Weighted upper domination number
- On distance-3 matchings and induced matchings
- 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
- Minimum maximal acyclic matching in proper interval graphs
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)
