Exact-Exponential Time and FPT Algorithms for the Stable Marriage Problem and its variants

dc.rights.license	CC-BY-NC-ND
dc.contributor.advisor	Nederlof, Jesper
dc.contributor.author	Yeh, Li-Wei
dc.date.accessioned	2025-10-15T23:03:19Z
dc.date.available	2025-10-15T23:03:19Z
dc.date.issued	2025
dc.identifier.uri	https://studenttheses.uu.nl/handle/20.500.12932/50548
dc.description.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.
dc.description.sponsorship	Utrecht University
dc.language.iso	EN
dc.subject	This thesis provides an exact-exponential time algorithm for the enumeration of stable matchings in a Stable Roommates Problem. It also presents an FPT algorithm parameterized by the parameter cutwidth, for Max-SMTI and other variations of the Stable Marriage Problem.
dc.title	Exact-Exponential Time and FPT Algorithms for the Stable Marriage Problem and its variants
dc.type.content	Master Thesis
dc.rights.accessrights	Open Access
dc.subject.courseuu	Computing Science
dc.thesis.id	54621