graph - 具有初始猜测的二部图快速最大匹配算法

Question

我正在研究一个二分匹配问题，我需要解决初始图，然后解决已删除不同节点的图的多个变体。目标是尽快解决所有变体，因此我想使用从解决原始图获得的信息来更快地解决变体。

我有使用单纯形法解决线性规划问题的经验，这得益于对解决方案的初始猜测，但我是二分匹配算法的新手。

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

Answer 1

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

归根结底，最有效的将取决于删除的具体内容；这些算法将获取您可能拥有的有关问题结构的任何知识。

但是，也许您的问题是离线算法足够好：如果G = ( V , E ) 是您开始的二分图，并且M是G的匹配项，并且如果G' = ( V' , E' )是通过删除一些顶点获得的图，因此E'是通过从E中删除所有与V \ V'中的顶点相关的边得到的，那么显然M ∩ E'是G的（不一定是最大的）匹配'，并且您正在寻求扩展它。最常见的最大匹配算法通过扩展现有匹配来工作（如果您愿意，可以使用原始可行解决方案）；这包括基于增强路径搜索的那些，因此您可以将具有受限匹配的那些作为输入，并且可能会很好。一个也很容易实现的具体经典示例是Hopcroft–Karp 算法。