Adapting stable matchings to forced and forbidden pairs

DOI10.1016/J.JCSS.2024.103579MaRDI QIDQ6627043FDOQ6627043

Niclas Boehmer, Klaus Heeger

Publication date: 29 October 2024

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

rotationsNP-hardnesspolynomial-time algorithmFPTstable marriageincremental algorithmsstable roommates\(\mathsf{W[1}\)-hardness]forced and forbidden pairs

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• College Admissions and the Stability of Marriage
• Algorithmics of Matching Under Preferences
• The Strongly Stable Roommates Problem
• An efficient algorithm for the “stable roommates” problem
• Incremental Clustering and Dynamic Information Retrieval
• Network flow and 2-satisfiability
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
• Hard variants of stable marriage.
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• The structure of stable marriage with indifference
• The stable marriage problem with restricted pairs.
• Efficient algorithms for generalized stable marriage and roommates problems
• A new fixed point approach for stable networks and stable marriages
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• The stable marriage problem with ties and restricted edges
• Characterisation of Strongly Stable Matchings
• Facility Location in Evolving Metrics
• Gradual college admission
• Scaling Algorithms for Weighted Matching in General Graphs
• Maintaining Near-Popular Matchings
• Deepening the (parameterized) complexity analysis of incremental stable matching problems

This page was built for publication: Adapting stable matchings to forced and forbidden pairs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6627043)