# Approximating maximum uniquely restricted matchings in bipartite graphs

1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by Golumbic, Hirst, and Lewenstein (2001) and studied in a number of articles. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs, namely those excluding a C4 or with maximum degree at most three. In particular, we achieve a ratio of 5/9 for subcubic bipartite graphs, improving over a 1/2-approximation algorithm proposed by Mishra (2011).
Keywords :
Document type :
Journal articles
Domain :

Cited literature [45 references]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02410617
Contributor : Ignasi Sau Connect in order to contact the contributor
Submitted on : Friday, December 13, 2019 - 10:03:28 PM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM

### Citation

Julien Baste, Dieter Rautenbach, Ignasi Sau Valls. Approximating maximum uniquely restricted matchings in bipartite graphs. Discrete Applied Mathematics, Elsevier, 2019, 267, pp.30-40. ⟨10.1016/j.dam.2019.04.024⟩. ⟨lirmm-02410617⟩

Record views