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

摘要：

设图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-困难性,基于匈牙利算法给出了该问题的近似算法.

关键词：R-二部图、R-可行匹配、R-可行覆盖、近似算法

所属期刊栏目：32

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2019-05-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：969-977