为什么blossom算法比Micali-Vazirani算法用得更好
Why is the blossom algorithm more well used than the Micali-Vazirani algorithm
据了解，Micali-Vazirani 算法 (1980) 在时间复杂度上显着 优于 blossom 算法 (1961)（Micali-Vazirani 是 O(V^{1/2} E) and blossom is O(V^2 E) for maximum cardinality matching in general graphs. Yet, the blossom seems to be much more widely used, even recently (). Even packages desinged to solve these problems implement blossom over Micali-Vazirani (1 ).这是为什么？
Micali-Vazirani 不支持权重，您从 networkx 链接的例程用于查找最大 weight 匹配。如果您的图是二分图并且您不需要权重，人们还会求助于更简单的 Hopcroft-Karp，它与 Micali-Vazirani 的界限相匹配，这也阻碍了它的普及。我认为，主要障碍是实施 Micali-Vazirani 的复杂性。
最大 weight 匹配的完全无条件技术水平并不比 Edmonds O(mn2) 好多少，那里是 HN Gabow 在 Data structures for weighted matching and nearest common ancestors with linking 中提出的 1990 年算法，其求解时间复杂度为 O(mn + n2 log n)。但是在这么小的加速下，算法的实现和常数因子规则的简单性。
如果您不介意近似值，那么 运行 Duan 和 Seth Pettie 在 2014 年的论文 Linear-Time Approximation for Maximum Weight Matching 中发现了一个有趣的复杂性（也包含对算法的很好的调查），它可以解决O(m/ɛ log(1/ɛ)) 时间的 (1-ɛ) 近似问题。也就是说，如果您可以接受匹配的权重，比方说，最大权重匹配的 10%，您将获得 O(m) 复杂度。
据了解，Micali-Vazirani 算法 (1980) 在时间复杂度上显着 优于 blossom 算法 (1961)（Micali-Vazirani 是 O(V^{1/2} E) and blossom is O(V^2 E) for maximum cardinality matching in general graphs. Yet, the blossom seems to be much more widely used, even recently (
Micali-Vazirani 不支持权重，您从 networkx 链接的例程用于查找最大 weight 匹配。如果您的图是二分图并且您不需要权重，人们还会求助于更简单的 Hopcroft-Karp，它与 Micali-Vazirani 的界限相匹配，这也阻碍了它的普及。我认为，主要障碍是实施 Micali-Vazirani 的复杂性。
最大 weight 匹配的完全无条件技术水平并不比 Edmonds O(mn2) 好多少，那里是 HN Gabow 在 Data structures for weighted matching and nearest common ancestors with linking 中提出的 1990 年算法，其求解时间复杂度为 O(mn + n2 log n)。但是在这么小的加速下，算法的实现和常数因子规则的简单性。
如果您不介意近似值，那么 运行 Duan 和 Seth Pettie 在 2014 年的论文 Linear-Time Approximation for Maximum Weight Matching 中发现了一个有趣的复杂性（也包含对算法的很好的调查），它可以解决O(m/ɛ log(1/ɛ)) 时间的 (1-ɛ) 近似问题。也就是说，如果您可以接受匹配的权重，比方说，最大权重匹配的 10%，您将获得 O(m) 复杂度。