Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier

DOI10.1016/j.disopt.2020.100593zbMath1506.05168arXiv1812.05930OpenAlexW3035789173MaRDI QIDQ2218644

Dieter Rautenbach, Julien Baste, Maximilian Fürst

Publication date: 15 January 2021

Published in: Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingapproximation algorithminduced matchingprimal-dual approximation algorithmstrong matching

Mathematics Subject Classification ID

Linear programming (90C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (1)

Approximating maximum acyclic matchings by greedy and local search strategies

Cites Work

• Unnamed Item
• Two greedy consequences for maximum induced matchings
• Induced matchings in bipartite graphs
• Approximability results for the maximum and minimum maximal induced matching problems
• Locally searching for large induced matchings
• Approximating weighted induced matchings
• On the approximability of the maximum induced matching problem
• Graphs of prescribed girth and bi-degree
• New results on maximum induced matchings in bipartite graphs and beyond
• Induced Matchings in Graphs of Bounded Maximum Degree
• Induced Matchings in Subcubic Graphs
• Approximation and Online Algorithms

This page was built for publication: Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier