Approximating maximum uniquely restricted matchings in bipartite graphs

DOI10.1016/j.dam.2019.04.024zbMath1419.05173OpenAlexW2944540875WikidataQ127926921 ScholiaQ127926921MaRDI QIDQ2322866

Julien Baste, Ignasi Sau, Dieter Rautenbach

Publication date: 5 September 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-02410617/file/App.pdf

zbMATH Keywords

bipartite graphapproximation algorithmuniquely restricted matchingsubcubic graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items

Matchings under distance constraints. I

Cites Work

• Unnamed Item
• Unnamed Item
• Induced matchings in subcubic graphs without short cycles
• On distance-3 matchings and induced matchings
• Induced matchings in bipartite graphs
• Matching theory
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• Induced matchings in intersection graphs.
• On maximum induced matchings in bipartite graphs
• On the Maximum Uniquely Restricted Matching for Bipartite Graphs
• VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS
• Unicycle graphs and uniquely restricted maximum matchings
• Graph Factors and Matching Extensions
• Graphs in which some and every maximum matching is uniquely restricted
• Induced matchings in cubic graphs
• Induced Matchings in Subcubic Planar Graphs
• Induced Matchings in Subcubic Graphs
• Uniquely restricted matchings

This page was built for publication: Approximating maximum uniquely restricted matchings in bipartite graphs