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

作     者：李伟娟 陈光亭 陈永 张安 LI Weijuan;CHEN Guangting;CHEN Yong;ZHANG An

作者机构：杭州电子科技大学理学院浙江杭州310018 

基　　金：国家自然科学基金资助项目(11571252 11401149) 浙江省自然科学基金资助项目(LY16A010015) 

出 版 物：《杭州电子科技大学学报（自然科学版）》 (Journal of Hangzhou Dianzi University：Natural Sciences)

年 卷 期：2017年第37卷第5期

页      码：97-99页

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

主 题 词：二部图 完美匹配 近似算法 最坏情况界 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

D　O　I：10.13954/j.cnki.hdu.2017.05.018

馆 藏 号：203267692...