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 metadatas

Cited literature [45 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02410617
Contributor : Ignasi Sau <>
Submitted on : Friday, December 13, 2019 - 10:03:28 PM
Last modification on : Wednesday, December 18, 2019 - 1:49:02 AM

File

Identifiers

Collections

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⟩

Share

Metrics

Record views

11

Files downloads

6