二部图中的完美匹配子集权的极小化问题

• 作者: 张安 李伟娟 陈光亭 陈永
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 二部图 完美匹配 近似算法 最坏情况界
• 年，卷（期）: 2017,（5）
• 页码范围: 97-99
• 页数: 3页
• 分类号: O221.7
• 语种: 中文
• DOI: 10.13954/j.cnki.hdu.2017.05.018

摘要

主要研究了二部图中的完美匹配子集权的极小化问题,针对完美匹配两个子集权的极小化问题,证明了最小权重优先算法SWF的最坏情况界为3/2,并应用一一互换思想,设计了最坏情况界至多为4/3的改进算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈光亭	杭州电子科技大学理学院	44	74	5.0	7.0
2	张安	杭州电子科技大学理学院	24	15	2.0	2.0
3	陈永	杭州电子科技大学理学院	22	14	2.0	2.0
4	李伟娟	杭州电子科技大学理学院	1	1	1.0	1.0