Two greedy consequences for maximum induced matchings

DOI10.1016/J.TCS.2015.08.002MaRDI QIDQ497673zbMATH OpenOpenAlexFDO

Authors Dieter Rautenbach

Publication date 25 September 2015

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3851125 (Why is no real title available?)
• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• A bound on the strong chromatic index of a graph
• Approximation and Online Algorithms
• Induced matchings
• Induced matchings in intersection graphs.
• Induced matchings in subcubic graphs
• Matching theory
• NP-completeness of some generalizations of the maximum matching problem
• New results on maximum induced matchings in bipartite graphs and beyond
• On distance-3 matchings and induced matchings
• On maximum induced matchings in bipartite graphs
• On the approximability of the maximum induced matching problem
• Strong chromatic index of 2-degenerate graphs

Cited in

(7)

• Approximating weighted induced matchings
• Approximating maximum acyclic matchings by greedy and local search strategies
• Degenerate matchings and edge colorings
• Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier
• Approximation and Online Algorithms
• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• 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)