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
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)
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