Approximating maximum uniquely restricted matchings in bipartite graphs
Approximating maximum uniquely restricted matchings in bipartite graphs
复制标题
近似二分图中的最大唯一限制匹配
DOI：
10.1016/j.dam.2019.04.024
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
I. Sau
中科院分区：
文献类型：
--
作者：
J. Baste;D. Rautenbach;I. Sau
如果没有其他匹配覆盖完全相同的顶点集，则图中的匹配是唯一受限的。这个概念是由Golumbic，Hirst和Lewenstein（2001）定义的，并在许多文章中进行了研究。我们提供近似算法计算的唯一限制匹配的最大尺寸在一些二部图，即那些不包括C4或最大程度最多为3。特别是，我们对亚三次二部图实现了5 9的比率，比Mishra（2011）提出的1 2近似算法有所改进。
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 C 4 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).
登录
查看更多内容
某些和每个最大匹配都受到唯一限制的图
影响因子：
0.9
作者：
L. Penso;D. Rautenbach;U. Souza
通讯作者：
U. Souza
区间图中的唯一限制匹配
影响因子：
0.8
作者：
Mathew C. Francis;Dalu Jacob;Satyabrata Jana
通讯作者：
Satyabrata Jana
独轮车图和唯一限制的最大匹配
DOI：
--
发表时间：
2005
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
Vadim E. Levit;Eugen Mandrescu
通讯作者：
Eugen Mandrescu
影响因子：
1.1
作者：
CAMERON, K
通讯作者：
CAMERON, K
关于距离 3 匹配和诱导匹配
影响因子：
1.1
作者：
A. Brandstädt;R. Mosca
通讯作者：
R. Mosca