带初始猜测的二部图快速最大匹配算法
Fast Maximum Matching Algorithm for Bipartite Graphs with Initial Guess
我正在处理一个二分匹配问题，我需要求解一个初始图，然后求解已移除不同节点的图的多个变体。目标是尽快解决所有变体，因此我想使用从解决原始图形中获得的信息来更快地解决变体。
我有使用单纯形法解决线性规划问题的经验，这得益于对解的初步猜测，但我是二分匹配算法的新手。
是否有可以利用初始猜测来加速求解器的二分匹配算法？
@sascha 提到的递减二分匹配应该有用；另一个可能有用的搜索关键字候选者是 "fully dynamic maximum mathing".
归根结底，最有效的方法取决于具体删除的内容；这些算法将采用您可能拥有的关于问题结构的任何知识。
但是，也许您的问题是离线算法就足够了：如果 G = (V, E)是你开始的二分图，M是G的匹配，如果 G' = (V', E')是去掉部分顶点得到的图，使得E' 是通过从 E 中删除与 V \ V' 中顶点关联的所有边得到的，然后显然 M ∩ E' 是 G' 的（不一定是最大）匹配，而你'正在寻求扩展。最常见的最大匹配算法通过扩展现有匹配（如果您愿意，可以使用原始可行解）来工作；这包括基于增强路径搜索的那些，因此您可以将其中一个具有限制匹配的作为输入，也许很好。一个也很容易实现的具体经典示例是 Hopcroft–Karp algorithm.
我正在处理一个二分匹配问题，我需要求解一个初始图，然后求解已移除不同节点的图的多个变体。目标是尽快解决所有变体，因此我想使用从解决原始图形中获得的信息来更快地解决变体。
我有使用单纯形法解决线性规划问题的经验，这得益于对解的初步猜测，但我是二分匹配算法的新手。
是否有可以利用初始猜测来加速求解器的二分匹配算法？
@sascha 提到的递减二分匹配应该有用；另一个可能有用的搜索关键字候选者是 "fully dynamic maximum mathing".
归根结底，最有效的方法取决于具体删除的内容；这些算法将采用您可能拥有的关于问题结构的任何知识。
但是，也许您的问题是离线算法就足够了：如果 G = (V, E)是你开始的二分图，M是G的匹配，如果 G' = (V', E')是去掉部分顶点得到的图，使得E' 是通过从 E 中删除与 V \ V' 中顶点关联的所有边得到的，然后显然 M ∩ E' 是 G' 的（不一定是最大）匹配，而你'正在寻求扩展。最常见的最大匹配算法通过扩展现有匹配（如果您愿意，可以使用原始可行解）来工作；这包括基于增强路径搜索的那些，因此您可以将其中一个具有限制匹配的作为输入，也许很好。一个也很容易实现的具体经典示例是 Hopcroft–Karp algorithm.