Approximability results for the maximum and minimum maximal induced matching problems

DOI10.1016/j.disopt.2007.11.010zbMath1140.90479OpenAlexW1985482016MaRDI QIDQ937401

Gerd Finke, Valery S. Gordon, Yury L. Orlovich, Igor Edm. 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

zbMATH Keywords

bipartite graphcombinatorial optimizationNP-completenessinduced matchingapproximability

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

On the computational complexity of the Helly number in the \(P_3\) and related convexities, Almost Induced Matching: Linear Kernels and Parameterized Algorithms, Graphs with maximal induced matchings of the same size, Exact algorithms for maximum induced matching, Weighted upper domination number, Complexity of finding maximum regular induced subgraphs with prescribed degree, Unnamed Item, Minimum maximal acyclic matching in proper interval graphs, On the complexity of minimum maximal acyclic matchings, Parameterized algorithms and kernels for almost induced matching, Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem, Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier, Well-indumatched Trees and Graphs of Bounded Girth, On minimum maximal distance-\(k\) matchings, Approximating weighted induced matchings, Approximating maximum acyclic matchings by greedy and local search strategies, On distance-3 matchings and induced matchings, The complexity of dissociation set problems in graphs, New kernels for several problems on planar graphs, The parameterized complexity of the induced matching problem, On Distance-3 Matchings and Induced Matchings, Moderately exponential time algorithms for the maximum induced matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Irredundancy in circular arc graphs
• On induced matchings
• Problems and results in combinatorial analysis and graph theory
• NP-completeness of some generalizations of the maximum matching problem
• Independent domination in chordal graphs
• Induced matchings
• Maximum induced matchings in graphs
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• 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
• On the approximability of the maximum induced matching problem
• Finding a maximum induced matching in weakly chordal graphs
• New results on induced matchings
• On the Complexity of General Graph Factor Problems
• Planar 3DM is NP-complete
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Graph Classes: A Survey
• Independent Sets in Asteroidal Triple-Free Graphs
• Bipartite Domination and Simultaneous Matroid Covers
• On the completeness of a generalized matching problem
• The P k Partition Problem and Related Problems in Bipartite Graphs
• Algorithms – ESA 2004
• The complexity of theorem-proving procedures
• Approximation and Online Algorithms