Exact-Exponential Time and FPT Algorithms for the Stable Marriage Problem and its variants
Files
Publication date
Authors
DOI
Document Type
Master Thesis
Metadata
Show full item recordCollections
License
CC-BY-NC-ND
Abstract
Stable matching problems, such as the Stable Roommates (SR) and Stable Marriage with Ties and Incomplete lists (SMTI), have numerous applications in economics and computer science. In this thesis, we provide a 2^O(n) time algorithm to enumerate all stable matchings in instances of SR, enabling optimization variants to run with the same time complexity. We also develop fixed-parameter tractable (FPT) algorithms parameterized by the cutwidth for matching problems, including Max-SMTI, Max-SRTI, and MaxC3DSMTI.