Robust recoverable perfect matchings
Robust recoverable perfect matchings
复制标题
DOI：
10.1002/net.21624
复制
发表时间：
2015-10
期刊：
影响因子：
2.1
通讯作者：
M. C. Dourado;D. Meierling;L. Penso;D. Rautenbach;Fábio Protti;Aline Ribeiro de Almeida
中科院分区：
文献类型：
--
作者：
M. C. Dourado;D. Meierling;L. Penso;D. Rautenbach;Fábio Protti;Aline Ribeiro de Almeida
我们研究图 G 中的完美匹配 M，它具有鲁棒性和可恢复性两个属性；其中，鲁棒性是指G的边数不多的集合F′的失效可以得到补偿，可恢复性是指这种补偿能够以有效的方式完成，即G−F′具有完美的匹配M′，其中M和M′的对称差很小。我们确定了几个相关算法问题的难度并确定了一些易于处理的情况。除其他外，我们还显示了众所周知的图匹配排除数的硬度。 © 2015 Wiley periodicals, Inc. 网络，卷。 66(3), 210–213 2015
We study perfect matchings M in graphs G that have the two properties of being robust as well as recoverable; where robust means that the failure of a set F ′ of not too many edges of G can be compensated, and recoverable means that this compensation can be done in an efficient way, that is, G − F ′ has a perfect matching M ′ for which the symmetric difference of M and M ′ is small. We establish the hardness of several related algorithmic problems and identify some tractable cases. Among others we show the hardness of the well known matching preclusion number of a graph. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 210–213 2015