Disjoint Stable Matchings in Linear Time

Autor:	Aadityan Ganesh, Geevarghese Philip, Prajakta Nimbhorkar, H. V. Vishwa Prakash
Rok vydání:	2021
Předmět:	Combinatorics Matching (graph theory) Bipartite graph Pairwise comparison Disjoint sets Characterization (mathematics) Stability (probability) Time complexity Mathematics
Zdroj:	Graph-Theoretic Concepts in Computer Science ISBN: 9783030868376 WG
DOI:	10.1007/978-3-030-86838-3_7
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::db98f3066d8d62a4227b3ed624e4348a https://doi.org/10.1007/978-3-030-86838-3_7 Zobrazit plný text záznamu