The Complexity of Counting Stable Marriages

DOI10.1137/0215048MaRDI QIDQ3751000zbMATHOpenAlexFDO

Authors Robert W. Irving, Paul Leather

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0215048

zbMATH Keywords

stable marriage problemstable matching

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of approximately counting stable matchings
• The Complexity of Approximately Counting Stable Matchings
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
• Complexity of the sex-equal stable marriage problem
• An efficient algorithm for the “stable roommates” problem

Cited in

(82)

• A unified approach to finding good stable matchings in the hospitals/residents setting
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• On the likely number of solutions for the stable marriage problem
• (Un)stable matchings with blocking costs
• The stable marriage problem with restricted pairs.
• The complexity of approximately counting stable roommate assignments
• Stable marriage with ties and bounded length preference lists
• On the invariance of male optimal stable matching
• Matching games with partial information
• Understanding the generalized median stable matchings
• Stable matchings and stable partitions^∗
• The complexity of the certification of properties of stable marriage
• How do I marry thee? Let me count the ways
• On the set of stable matchings in a bipartite graph
• Linear programming brings marital bliss
• Size Versus Stability in the Marriage Problem
• Stable allocations and partially ordered sets
• The graphs of stably matchable pairs
• Review of the theory of stable matchings and contract systems
• Network flow and 2-satisfiability
• An algorithm to compute the full set of many-to-many stable matchings.
• Polyhedral aspects of stable marriage
• A deferred acceptance algorithm with contracts
• Polynomial time algorithm for an optimal stable assignment with multiple partners
• Cycles to compute the full set of many-to-many stable matchings
• Efficient algorithms for generalized stable marriage and roommates problems
• Deferred acceptance with compensation chains
• The singleton core in the college admissions problem and its application to the national resident matching program (NRMP)
• An efficient algorithm for batch stability testing
• The complexity of approximately counting stable matchings
• Bistable versions of the marriages and roommates problems
• A characterization of strongly stable fractional matchings
• Essentially stable matchings
• The stable marriage problem: an interdisciplinary review from the physicist's perspective
• On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women
• A counterexample of size 20 for the problem of finding a 3-dimensional stable matching with cyclic preferences
• Finding a Level Ideal of a Poset
• A unifying approach to the structures of the stable matching problems
• Parametric stable marriage and minimum cuts
• Circular stable matching and 3-way kidney transplant
• Jointly stable matchings
• Hardness results on the man-exchange stable marriage problem with short preference lists
• Jointly stable matchings
• On the set of many-to-one strongly stable fractional matchings
• The Generalized Median Stable Matchings: Finding Them Is Not That Easy
• The structure of stable marriage with indifference
• On the stable \(b\)-matching problem in multigraphs
• Blockers and antiblockers of stable matchings
• Sex-equal stable matchings: complexity and exact algorithms
• The stable marriage problem with master preference lists
• Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings
• scientific article; zbMATH DE number 1405659 (Why is no real title available?)
• A fast algorithm for the generalized parametric minimum cut problem and applications
• Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
• A number of stable matchings in models of the Gale-Shapley type
• The lattice of envy-free matchings
• Disjoint stable matchings in linear time
• Stable matching problems with exchange restrictions
• Matching with preferences over colleagues solves classical matching
• The algebra of stable marriages
• A new fixed point approach for stable networks and stable marriages
• Size versus stability in the marriage problem
• Descending the stable matching lattice: how many strategic agents are required to turn pessimality to optimality?
• The diameter of the stable marriage polytope: bounding from below
• Coalitional permutation manipulations in the Gale-Shapley algorithm
• A stable marriage requires communication
• Stability and stabilisation of networked pairing problem via event-triggered control
• Entering classes in the college admissions model
• Stable matching with special preference patterns
• The lattice of envy-free many-to-many matchings with contracts
• Complexity study for the robust stable marriage problem
• The losses from integration in matching markets can be large
• scientific article; zbMATH DE number 7378730 (Why is no real title available?)
• On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
• Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case
• Affinely representable lattices, stable matchings, and choice functions
• On stable assignments generated by choice functions of mixed type
• Counterexamples of small size for three-sided stable matching with cyclic preferences
• Unique stable matchings
• On a many-sided matching problem with mixed preferences
• Finding all stable matchings with assignment constraints
• Affinely representable lattices, stable matchings, and choice functions

This page was built for publication: The Complexity of Counting Stable Marriages

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