Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
复制标题
正则二分图中的最小最大匹配是 NP 困难的
DOI：
10.1007/978-3-540-79228-4_32
复制
发表时间：
2008
期刊：
影响因子：
1.1
通讯作者：
T. Ekim
中科院分区：
文献类型：
--
作者：
M. Demange;T. Ekim
Yannakakis和Gavril在[10]中指出，在最大度为3的二部图或最大度为3的平面图中，寻找最小尺寸的最大匹配（简称MMM），也称为最小边控制集，是NP-困难的。Horton和Kilakos将这一结果推广到平面二部图和平面三部图[6]。本文推广了Yannakakis和Gavril在文献[10]中的结果，证明了对于k ≥ 3的固定值，MMM在k-正则二部图类中是NP-困难的.
Yannakakis and Gavril showed in [10] that the problem of finding a maximal matching of minimum size (MMM for short), also called Minimum Edge Dominating Set, is NP-hard in bipartite graphs of maximum degree 3 or planar graphs of maximum degree 3. Horton and Kilakos extended this result to planar bipartite graphs and planar cubic graphs [6]. Here, we extend the result of Yannakakis and Gavril in [10] by showing that MMM is NP-hard in the class of k-regular bipartite graphs for all k ≥ 3 fixed.