R-二部图上的R-可行匹配问题

R-feasible matching problem on R-bipartite graphs

设图G=(V, E)有边子集RE若G′=(V,E-R)是具有二分类(X,Y)的二部图,则称图G是R-二部图.对图G的匹配M,若由所有M饱和点导出的子图不包含R中的边,则称M是R-可行匹配.先讨论R-二部图上的R-可行匹配数与R-可行覆盖数的关系和一类特殊R-二部图上的R-可行匹配数,然后证明了R-二部图上的R-可行匹配问题的NP-困难性,基于匈牙利算法给出了该问题的近似算法.

Let G=(V,E)be a graph and R■E.We say that G is R-bipartite with bipartite sets X and Y if the graph G′=(V,E?R)is bipartite with bipartite sets X and Y.A matching M in G is called R-feasible if the subgraph induced by the M-saturated vertices does not have an edge of R.In this paper,we first study the relationship of the R-feasible matching number and the R-feasible cover number,and the R-feasible matching number of a special R-bipartite graph.Then,we prove that the R-feasible matching problem is NP-hard for R-bipartite graph.Based the Hungarian algorithm,we present an approximation algorithm for the R-feasible matching problem.