无向图的边极大匹配并行算法及其应用

下载PDF

导出

摘要在ＥＲＥＷＰＲＡＭ（ｅｘｃｌｕｓｉｖｅ－ｒｅａｄａｎｄｅｘｃｌｕｓｉｖｅ－ｗｒｉｔｅｐａｒａｌｅｌｒａｎｄｏｍａｃｅｓｍａｃｈｉｎｅ）并行计算模型上，对范围很广的一类无向图的边极大匹配问题，给出时间复杂性为Ｏ（ｌｏｇｎ），使用Ｏ（（ｎ＋ｍ）／ｌｏｇｎ）处理器的最佳。

作者马军岩间一雄顾谦平

机构地区山东大学计算机科学系京都大学计算机科学系会津大学软件系

出处《软件学报》 EI CSCD 北大核心 1999年第1期107-110,共4页 Journal of Software

基金国家自然科学基金国家863高科技项目基金山东省自然科学基金山东大学跨世纪人才基金

关键词边极大匹配无向图图论并行算法

1马军,刘振法.图的极大匹配并行算法[J].山东大学学报（自然科学版）,1999,34(1):41-47.
2谢应泰.化简布尔式的一个图论方法[J].成都大学学报（自然科学版）,1993,12(1):37-41.
3王世英,刘岩,张卓奎.完全可匹配图(英文)[J].郑州大学学报（理学版）,1999,33(2):9-12.
4王文虎,杨雨.二部图的所有极大匹配[J].电脑开发与应用,2011,24(8):11-12.
5徐凤生.二部图所有极大匹配的求解算法[J].福建电脑,2005,21(8):45-45. 被引量：1
6徐扬,唐毅,文振焜,刘斌.针对高速交换结构的广义极大匹配调度算法[J].电子学报,2007,35(10):1809-1816. 被引量：2
7吴廷增.图的极大匹配能(英文)[J].华东师范大学学报（自然科学版）,2015(1):136-141.
8赵卫星,李秋,王秀欣.基于优先级输入排队的调度算法的研究[J].中国科技信息,2008(16):34-35. 被引量：2
9V.L.Chernyak.Exclusive γ^(*)γ processes[J].Chinese Physics C,2010,34(6):822-830.
10何秉姣,汪红.一种新的CRC16算法及其在通信系统中的应用[J].中南民族大学学报（自然科学版）,2012,31(4):105-107.

软件学报

1999年第1期

浏览历史

内容加载中请稍等...