Stable matching games: manipulation via subgraph isomorphism

DOI10.1007/S00453-017-0382-5zbMATH Open1393.68072OpenAlexW2766788849MaRDI QIDQ722540FDOQ722540

Authors: Sushmita Gupta, Sanjukta Roy 

Publication date: 26 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6864/

Recommendations

• Stable matching games: manipulation via subgraph isomorphism
• Sex-equal stable matchings: complexity and exact algorithms
• Cheating strategies for the Gale-Shapley algorithm with complete preference lists
• Stable matching problems with exchange restrictions
• The exchange-stable marriage problem

zbMATH Keywords

stable matchingmanipulationsubgraph isomorphismexact-exponential time algorithmsGale-Shapley algorithmsuitor graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

Cites Work

• Title not available (Why is that?)
• Exact exponential algorithms.
• Representative sets of product families
• Title not available (Why is that?)
• Parameterized algorithms
• College Admissions and the Stability of Marriage
• On the complexity of \(k\)-SAT
• Ms. Machiavelli and the Stable Matching Problem
• The number of trees
• Faster algorithms for finding and counting subgraphs
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• Stable assignment with couples: parameterized complexity and local search
• Counting subgraphs via homomorphisms
• Constant Time Generation of Rooted Trees
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Cheating strategies for the Gale-Shapley algorithm with complete preference lists
• Stable marriage and roommates problems with restricted edges: complexity and approximability

Cited In (3)

• Stable matching games: manipulation via subgraph isomorphism
• Manipulating the outcome of stable marriage and roommates problems
• The minimum set of \(\mu\)-compatible subgames for obtaining a stable set in an assignment game

This page was built for publication: Stable matching games: manipulation via subgraph isomorphism

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