A formal theory for the complexity class associated with the stable marriage problem

DOI10.4230/LIPICS.CSL.2011.381MaRDI QIDQ2915696zbMATH OpenOpenAlexFDO

Authors Dai Tri Man Lê, Yuli Ye, Stephen Cook

Publication date 18 September 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_2d07.html

zbMATH Keywords

complexity theorybounded arithmeticcomparator circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Complexity study for the robust stable marriage problem
• scientific article; zbMATH DE number 45086
• On the complexity of robust stable marriage
• Hardness and approximation results for some variants of stable marriage problem
• Approximability results for stable marriage problems with ties.
• Complexity of the sex-equal stable marriage problem
• On the decomposability of the stable marriage problem
• Lower Bounds for the Stable Marriage Problem and Its Variants
• Stable marriage with covering constraints -- a complete computational trichotomy
• Better and simpler approximation algorithms for the stable marriage problem

Cited in

(2)

• Stable marriage with covering constraints -- a complete computational trichotomy
• The complexity of the comparator circuit value problem

This page was built for publication: A formal theory for the complexity class associated with the stable marriage problem

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