二分图取大匹配问题的分布式算法

摘要

本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n^2+m))、时间复杂性为 O(n^3);第二个算法的通讯复杂性为O(n^(1/2)(n^2+m))、时间复杂性为O(n^(5/2)),这里n和m分别为二分图的结点个数及边的数目。关于这一问题的分布式算法目前尚未见诸报导,这里建议的算法很可能是此问题的第一个分布式算法。