The Complexity of Counting Stable Marriages

DOI10.1137/0215048zbMATH Open0611.68015OpenAlexW1981139087MaRDI QIDQ3751000FDOQ3751000

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

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

zbMATH Keywords

stable marriage problemstable matching

Mathematics Subject Classification ID

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

Cited In (84)

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

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)