Adapting stable matchings to forced and forbidden pairs

DOI10.1016/J.JCSS.2024.103579MaRDI QIDQ6627043

Niclas Boehmer, Klaus Heeger

Publication date: 29 October 2024

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

zbMATH Keywords

rotationspolynomial-time algorithmNP-hardnessFPTstable marriageincremental algorithmsstable roommates\(\mathsf{W[1}\)-hardness]forced and forbidden pairs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) 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?)
• The stable marriage problem with ties and restricted edges
• Efficient algorithms for generalized stable marriage and roommates problems
• A new fixed point approach for stable networks and stable marriages
• Network flow and 2-satisfiability
• The stable marriage problem with restricted pairs.
• Hard variants of stable marriage.
• The structure of stable marriage with indifference
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Gradual college admission
• Maintaining Near-Popular Matchings
• An efficient algorithm for the “stable roommates” problem
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
• Scaling Algorithms for Weighted Matching in General Graphs
• Characterisation of Strongly Stable Matchings
• The Strongly Stable Roommates Problem
• Incremental Clustering and Dynamic Information Retrieval
• Reducibility among Combinatorial Problems
• Facility Location in Evolving Metrics
• Algorithmics of Matching Under Preferences
• College Admissions and the Stability of Marriage
• 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)