The complexity of the certification of properties of stable marriage

DOI10.1016/J.IPL.2004.09.006zbMATH Open1172.91334OpenAlexW2156629035MaRDI QIDQ834962FDOQ834962

Daniel J. Dougherty, Stanley Selkow

Publication date: 27 August 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.09.006

zbMATH Keywords

computational complexitycombinatorial problemsstable marriagecertificate complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Cites Work

• Title not available (Why is that?)
• College Admissions and the Stability of Marriage
• Complexity measures and decision tree complexity: a survey.
• Lower Bounds for the Stable Marriage Problem and Its Variants

Cited In (3)

• Title not available (Why is that?)
• Research and development of fringe projection-based methods in 3D shape reconstruction
• A nonconstructive elementary proof of the existence of stable marriages

   Recommendations

• Lower Bounds for the Stable Marriage Problem and Its Variants 👍 👎
• A stable marriage requires communication 👍 👎
• A Stable Marriage Requires Communication 👍 👎
• The Complexity of Counting Stable Marriages 👍 👎
• Complexity of the sex-equal stable marriage problem 👍 👎

This page was built for publication: The complexity of the certification of properties of stable marriage

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