Locally searching for large induced matchings

DOI10.1016/j.tcs.2018.02.006zbMath1388.68230arXiv1708.02028OpenAlexW2742438336MaRDI QIDQ1704586

Maximilian Fürst, Dieter Rautenbach, Marilena Leichter

Publication date: 12 March 2018

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

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

zbMATH Keywords

local searchinduced matchingstrong matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier ⋮ Approximating maximum acyclic matchings by greedy and local search strategies

Cites Work

• Unnamed Item
• Two greedy consequences for maximum induced matchings
• On distance-3 matchings and induced matchings
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings in intersection graphs.
• 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
• On maximum induced matchings in bipartite graphs
• New results on maximum induced matchings in bipartite graphs and beyond
• Approximation and Online Algorithms

This page was built for publication: Locally searching for large induced matchings