Two greedy consequences for maximum induced matchings

DOI10.1016/J.TCS.2015.08.002zbMATH Open1329.68294arXiv1507.04145OpenAlexW1848511982MaRDI QIDQ497673FDOQ497673

Authors: Dieter Rautenbach 

Publication date: 25 September 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We prove that, for every integer $d$ with $dgeq3$, there is an approximation algorithm for the maximum induced matching problem restricted to $C_3,C_5$-free $d$-regular graphs with performance ratio $$, which answers a question posed by Dabrowski et al. (Theor. Comput. Sci. 478 (2013) 33-40). Furthermore, we show that every graph with $m$ edges that is $k$-degenerate and of maximum degree at most $d$ with $k<d$, has an induced matching with at least $m/((3k-1)d-k(k+1)+1)$ edges.

Full work available at URL: https://arxiv.org/abs/1507.04145

Recommendations

• Approximation and Online Algorithms
• Locally searching for large induced matchings
• On the approximability of the maximum induced matching problem
• Publication:4944970
• Combinatorial Geometry and Graph Theory

zbMATH Keywords

approximation algorithmgreedy algorithminduced matchingstrong chromatic indexdegenerate graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Matching theory
• Induced matchings in subcubic graphs
• A bound on the strong chromatic index of a graph
• Induced matchings
• On maximum induced matchings in bipartite graphs
• NP-completeness of some generalizations of the maximum matching problem
• New results on maximum induced matchings in bipartite graphs and beyond
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the approximability of the maximum induced matching problem
• Induced matchings in intersection graphs.
• On distance-3 matchings and induced matchings
• Strong chromatic index of 2-degenerate graphs
• Approximation and Online Algorithms

Cited In (7)

• Approximating weighted induced matchings
• Approximating maximum acyclic matchings by greedy and local search strategies
• Approximation and Online Algorithms
• Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier
• Degenerate matchings and edge colorings
• Title not available (Why is that?)
• Locally searching for large induced matchings

This page was built for publication: Two greedy consequences for maximum induced matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q497673)