在一个完全二部图中找到第二个最大权重匹配

Question

给定一个赋权完全二部图G=(V，U，E)，最大赋权二部匹配问题，即指派问题，目的是在G中寻找一个边权和最大化的匹配。我知道有一些方法(例如匈牙利算法)可以解决这个问题。现在，我想解决一个稍微不同的问题：

给定一个加权完全二部图G=(V，U，E)，我想同时找到G中的最大加权二部匹配和第二大加权二部匹配。任何想法都将不胜感激。

Answer 1

有一个称为Lawler-Murty的通用算法，它允许您在连续调用中找到组合算法(包括匹配)的前K个答案。https://core.ac.uk/download/pdf/82129717.pdf在匹配的上下文中对其进行了描述。

基本上，在找到最佳答案后，您将约束添加到问题中，从而创建了许多子问题，从而排除了到目前为止找到的答案，但所有其他答案仍将成为其中一个子问题的答案。第二个最佳答案将成为其中一个子问题的最佳答案。当你反复这样做的时候，你最终会得到一棵大树上的子问题来解决。对于匹配问题，您可以通过利用以前问题中的一些工作来减少解决子问题所需的时间。