The Complexity of Counting Stable Marriages
From MaRDI portal
Publication:3751000
DOI10.1137/0215048zbMath0611.68015OpenAlexW1981139087MaRDI QIDQ3751000
Paul Leather, Robert W. Irving
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
Related Items
The structure of stable marriage with indifference ⋮ Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings ⋮ Matching games with partial information ⋮ Polynomial time algorithm for an optimal stable assignment with multiple partners ⋮ How do I marry thee? Let me count the ways ⋮ Hardness results on the man-exchange stable marriage problem with short preference lists ⋮ Blockers and antiblockers of stable matchings ⋮ On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Stable matchings and stable partitions∗ ⋮ Stability and stabilisation of networked pairing problem via event-triggered control ⋮ Finding a Level Ideal of a Poset ⋮ Linear programming brings marital bliss ⋮ Stable matching with special preference patterns ⋮ Essentially stable matchings ⋮ Descending the stable matching lattice: how many strategic agents are required to turn pessimality to optimality? ⋮ Disjoint stable matchings in linear time ⋮ The graphs of stably matchable pairs ⋮ Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case ⋮ Subquadratic algorithms for succinct stable matching ⋮ Cycles to compute the full set of many-to-many stable matchings ⋮ Review of the theory of stable matchings and contract systems ⋮ Complexity study for the robust stable marriage problem ⋮ Counterexamples of small size for three-sided stable matching with cyclic preferences ⋮ On the set of stable matchings in a bipartite graph ⋮ Jointly stable matchings ⋮ Stable allocations and partially ordered sets ⋮ The lattice of envy-free many-to-many matchings with contracts ⋮ Unique stable matchings ⋮ A deferred acceptance algorithm with contracts ⋮ Unnamed Item ⋮ The complexity of approximately counting stable roommate assignments ⋮ The complexity of approximately counting stable matchings ⋮ Parametric stable marriage and minimum cuts ⋮ A counterexample of size 20 for the problem of finding a 3-dimensional stable matching with cyclic preferences ⋮ Entering classes in the college admissions model ⋮ Understanding the generalized median stable matchings ⋮ An efficient algorithm for batch stability testing ⋮ Circular stable matching and 3-way kidney transplant ⋮ On the invariance of male optimal stable matching ⋮ A number of stable matchings in models of the Gale-Shapley type ⋮ The stable marriage problem with restricted pairs. ⋮ An algorithm to compute the full set of many-to-many stable matchings. ⋮ Bistable versions of the marriages and roommates problems ⋮ A unified approach to finding good stable matchings in the hospitals/residents setting ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ A fast algorithm for the generalized parametric minimum cut problem and applications ⋮ On the Likely Number of Solutions for the Stable Marriage Problem ⋮ The lattice of envy-free matchings ⋮ On the stable \(b\)-matching problem in multigraphs ⋮ A new fixed point approach for stable networks and stable marriages ⋮ Sex-equal stable matchings: complexity and exact algorithms ⋮ Size versus stability in the marriage problem ⋮ The singleton core in the college admissions problem and its application to the national resident matching program (NRMP) ⋮ Matching with preferences over colleagues solves classical matching ⋮ On the set of many-to-one strongly stable fractional matchings ⋮ Size Versus Stability in the Marriage Problem ⋮ A stable marriage requires communication ⋮ Efficient algorithms for generalized stable marriage and roommates problems ⋮ The Generalized Median Stable Matchings: Finding Them Is Not That Easy ⋮ The stable marriage problem with master preference lists ⋮ Affinely representable lattices, stable matchings, and choice functions ⋮ Affinely representable lattices, stable matchings, and choice functions ⋮ Stable matching problems with exchange restrictions ⋮ On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women ⋮ The diameter of the stable marriage polytope: bounding from below ⋮ A characterization of strongly stable fractional matchings ⋮ (Un)stable matchings with blocking costs ⋮ Coalitional permutation manipulations in the Gale-Shapley algorithm ⋮ Stable marriage with ties and bounded length preference lists ⋮ Every finite distributive lattice is a set of stable matchings for a small stable marriage instance ⋮ Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems ⋮ Unnamed Item ⋮ On Vertices and Facets of Combinatorial 2-Level Polytopes ⋮ Deferred Acceptance with Compensation Chains ⋮ Polyhedral Aspects of Stable Marriage ⋮ The losses from integration in matching markets can be large ⋮ Network flow and 2-satisfiability ⋮ A unifying approach to the structures of the stable matching problems
