Stable matching games: manipulation via subgraph isomorphism

DOI10.1007/s00453-017-0382-5zbMath1393.68072OpenAlexW2766788849MaRDI QIDQ722540

Sanjukta Roy, Sushmita Gupta

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 matchingsubgraph isomorphismmanipulationexact-exponential time algorithmsGale-Shapley algorithmsuitor graph

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Faster algorithms for finding and counting subgraphs
• Stable assignment with couples: parameterized complexity and local search
• Exact exponential algorithms.
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Cheating strategies for the Gale-Shapley algorithm with complete preference lists
• The number of trees
• Representative Sets of Product Families
• Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability
• Ms. Machiavelli and the Stable Matching Problem
• Constant Time Generation of Rooted Trees
• Algorithmics of Matching Under Preferences
• Parameterized Algorithms
• Counting Subgraphs via Homomorphisms
• College Admissions and the Stability of Marriage
• On the complexity of \(k\)-SAT

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