Two greedy consequences for maximum induced matchings

DOI10.1016/J.TCS.2015.08.002zbMath1329.68294arXiv1507.04145OpenAlexW1848511982MaRDI QIDQ497673

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

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

Related Items (5)

Locally searching for large induced matchings ⋮ Degenerate matchings and edge colorings ⋮ Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier ⋮ Approximating weighted induced matchings ⋮ Approximating maximum acyclic matchings by greedy and local search strategies

Cites Work

• Unnamed Item
• Unnamed Item
• On distance-3 matchings and induced matchings
• Matching theory
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• A bound on the strong chromatic index of a graph
• Induced matchings in intersection graphs.
• 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
• Strong Chromatic Index of 2-Degenerate Graphs
• Induced Matchings in Subcubic Graphs
• Approximation and Online Algorithms

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