Stable matching games: manipulation via subgraph isomorphism

DOI10.1007/S00453-017-0382-5MaRDI QIDQ722540zbMATH OpenOpenAlexFDO

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/

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)

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

Cites work

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

Cited in

(3)

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

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)