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

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

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

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)