Stable matching games: manipulation via subgraph isomorphism
DOI10.1007/s00453-017-0382-5zbMath1393.68072OpenAlexW2766788849MaRDI QIDQ722540
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/
stable matchingsubgraph isomorphismmanipulationexact-exponential time algorithmsGale-Shapley algorithmsuitor graph
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
