Skip to Main content Skip to Navigation
Journal articles

Approximating maximum uniquely restricted matchings in bipartite graphs

Julien Baste 1 Dieter Rautenbach 2 Ignasi Sau Valls 1 
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).
Document type :
Journal articles
Complete list of metadata

Cited literature [45 references]  Display  Hide  Download
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





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


Files downloads