Parameterized algorithms for stable matching with ties and incomplete lists
From MaRDI portal
Publication:1708024
DOI10.1016/J.TCS.2018.03.015zbMATH Open1392.68196OpenAlexW2791358809WikidataQ130085949 ScholiaQ130085949MaRDI QIDQ1708024FDOQ1708024
Authors: Deeksha Adil, Sushmita Gupta, Sanjukta Roy, Saket Saurabh, Meirav Zehavi 
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
Recommendations
- A \((1 + 1/e)\)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists
- scientific article; zbMATH DE number 1003296
- A sublinear parallel algorithm for stable matching
- Approximating stable matchings with ties of bounded size
- Parameterized algorithms for inclusion of linear matchings
- Mathematical models for stable matching problems with ties and incomplete lists
- Faster and simpler approximation of stable matchings
- Faster and simpler approximation of stable matchings
Cites Work
- Fundamentals of parameterized complexity
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- NP-complete stable matching problems
- Title not available (Why is that?)
- Parameterized algorithms
- College Admissions and the Stability of Marriage
- Quickly excluding a planar graph
- A Separator Theorem for Planar Graphs
- Minimum Edge Dominating Sets
- Hard variants of stable marriage.
- Parameterized complexity and local search approaches for the stable marriage problem with ties
- Stable marriage and indifference
- The structure of stable marriage with indifference
- A 3/2-Approximation Algorithm for General Stable Marriage
- Stable marriage with ties and bounded length preference lists
- Polynomial kernels for hard problems on disk graphs
Cited In (10)
- On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
- Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
- Solving hard stable matching problems involving groups of similar agents
- Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective
- Algorithms and complexity of strongly stable non-crossing matchings
- Slim tree-cut width
- Balanced stable marriage: how close is close enough?
- Balanced stable marriage: how close is close enough?
- Parameterized complexity and local search approaches for the stable marriage problem with ties
- Effective data reduction for strongly stable matching in very sparse graphs
This page was built for publication: Parameterized algorithms for stable matching with ties and incomplete lists
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1708024)
