Journal Articles Discrete Applied Mathematics Year : 2019

Approximating maximum uniquely restricted matchings in bipartite graphs

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).
Fichier principal
Vignette du fichier
App.pdf (432) Télécharger le fichier
Loading...

Dates and versions

lirmm-02410617 , version 1 (13-12-2019)

Identifiers

Cite

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

Altmetric

Share

More