论文标题
在线性时间内脱节稳定匹配
Disjoint Stable Matchings in Linear Time
论文作者
论文摘要
我们表明，给定一个SM实例G作为输入，我们可以在输入大小中找到最大的成对边缘 - 界限稳定匹配的g。这扩展了两个经典结果： 1。大风 - 夏普利算法，最多可以在线性时间中找到G的G级稳定匹配，并且 2。在双分部分图中找到最大的成对边缘 - 偶会完美匹配（无稳定性要求）的多项式时间算法，通过将König的表征与Tutte的F-Factor算法相结合而获得。 此外，我们还提供了一种算法，以列举给定实例稳定匹配的晶格中的所有最大长度链。该算法将时间多项式在输入大小中进行列举，以列举每个链。我们还在稳定匹配的随机实例中得出了预期的此类链数。
We show that given a SM instance G as input we can find a largest collection of pairwise edge-disjoint stable matchings of G in time linear in the input size. This extends two classical results: 1. The Gale-Shapley algorithm, which can find at most two ("extreme") pairwise edge-disjoint stable matchings of G in linear time, and 2. The polynomial-time algorithm for finding a largest collection of pairwise edge-disjoint perfect matchings (without the stability requirement) in a bipartite graph, obtained by combining König's characterization with Tutte's f-factor algorithm. Moreover, we also give an algorithm to enumerate all maximum-length chains of disjoint stable matchings in the lattice of stable matchings of a given instance. This algorithm takes time polynomial in the input size for enumerating each chain. We also derive the expected number of such chains in a random instance of Stable Matching.
