初值二部图的快速最大匹配算法

Question

我正在处理一个二分匹配问题，在这个问题中，我需要求解一个初始图，然后求解多个不同节点被移除的图的变体。我们的目标是尽快解决所有的变体，所以我想使用从求解原始图中获得的信息来更快地解决这些变体。

我有用单纯形法求解线性规划问题的经验，这得益于对解的初步猜测，但我对二分匹配算法还不熟悉。

是否有一种二部匹配算法，可以利用初始猜测来加快求解速度？

Answer 1

@sascha提到衰老的二分匹配应该是有用的；搜索关键字的另一个可能有用的候选是“完全动态的最大匹配”。

到头来，什么最有效将取决于到底删除了什么；算法将获取有关问题结构的任何知识。

但是，也许你的问题是离线算法是足够好的:如果G = (V，E)是你开始的二分图，M是G的匹配，如果G‘= (V'，E')是通过移除一些顶点得到的图，那么E’就是从E中移除所有与V‘中顶点相关的边得到的，那么很明显M∩E’是G‘的一个(不一定是最大的)匹配，你想要扩展它。最常见的最大匹配算法是通过扩展现有匹配来工作的(如果您愿意的话，可以使用原始可行的解决方案)；这包括那些基于增强路径搜索的算法，因此您可以将那些有限制匹配的算法中的一种作为输入，并且可能是好的选择。一个同样易于实现的具体经典示例是Hopcroft-Karp算法。