Dynamic Maximal Matching in Clique Networks

我们考虑在图拓扑批量动态变化的情况下，使用分布式算法计算最大匹配的问题。我们假设一个$n$个节点的图被分成$k$个部分，这些部分通过消息传递进行通信。我们的目标是提供一种高效的算法，即使在敌手确定$\ell$个边插入或删除的批处理的情况下，也可以快速更新匹配。 假设每轮链接带宽为$O(\beta\log n)$比特，对于参数$\beta\geq1$，我们首先证明了一个$\Omega(\frac{\ell\,\log k}{\beta\,k^2\log n})$轮的下界，假设一个无知的敌手不知道初始（随机）顶点分区以及玩家的当前状态，并且针对自适应敌手，我们证明了一个更强的下界为$\Omega(\frac{\ell}{\beta\,k\log n})$轮，自适应敌手可能最初选择任何平衡（但不一定是随机的）顶点分区，并且知道玩家的当前状态。 我们还提出了一个随机算法，其初始化时间为$O(\lceil\frac{n}{\beta\,k}\rceil\log n)$轮，同时实现了与$n$无关的更新时间：更具体地说，对于无知敌手，更新时间为$O(\lceil\frac{\ell}{\beta\,k}\rceil\log(\beta\,k))$轮，敌手必须提前确定所有更新。如果我们考虑更强的自适应敌手，则更新时间变为$O(\lceil\frac{\ell}{\sqrt{\beta\,k}}\rceil\log(\beta\,k))$轮。

分布式算法下的图匹配问题，如何在动态变化的图拓扑中快速更新匹配？

提出了一种随机化算法，可以在较短的时间内更新匹配，同时还给出了针对无差别和自适应对手的下界。

算法具有较好的时间复杂度和初始化时间，并且可以应对动态变化的图拓扑。论文还给出了下界和对手模型的分析。

近期的相关研究包括分布式算法中的其他图匹配问题，例如最大权匹配和最小顶标匹配。