Disjoint Stable Matchings in Linear Time
2021
We show that given a Stable Matching 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 Konig’s characterization with Tutte’s \(f\)-factor algorithm.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
0
Citations
NaN
KQI