二分图最大匹配问题的分布式算法 |
| |
作者姓名: | 唐策善 梁维发 |
| |
作者单位: | 中国科技大学计算机系,中国科技大学计算机系 |
| |
基金项目: | 国家863计划资金资助 |
| |
摘 要: | 本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n~2+m))、时间复杂性为 O(n~3);第二个算法的通讯复杂性为O(n~(1/2)(n~2+m))、时间复杂性为O(n~(5/2)),这里n和m分别为二分图的结点个数及边的数目。关于这一问题的分布式算法目前尚未见诸报导,这里建议的算法很可能是此问题的第一个分布式算法。
|
本文献已被 CNKI 等数据库收录! |
|