Parameterized algorithms for stable matching with ties and incomplete lists

DOI10.1016/j.tcs.2018.03.015zbMath1392.68196OpenAlexW2791358809WikidataQ130085949 ScholiaQ130085949MaRDI QIDQ1708024

Meirav Zehavi, Saket Saurabh, Sanjukta Roy, Deeksha Adil, Sushmita Gupta

Publication date: 4 April 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.03.015

zbMATH Keywords

stable matchingparameterized complexitypreference list

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Matching models (91B68)

Related Items (5)

On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Algorithms and complexity of strongly stable non-crossing matchings ⋮ Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Stable marriage with ties and bounded length preference lists
• Stable marriage and indifference
• Quickly excluding a planar graph
• Hard variants of stable marriage.
• The structure of stable marriage with indifference
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Minimum Edge Dominating Sets
• NP-complete stable matching problems
• Polynomial Kernels for Hard Problems on Disk Graphs
• A 3/2-Approximation Algorithm for General Stable Marriage
• A Separator Theorem for Planar Graphs
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• College Admissions and the Stability of Marriage

This page was built for publication: Parameterized algorithms for stable matching with ties and incomplete lists