Popular Roommates in Simply Exponential Time.

DOI10.4230/LIPICS.FSTTCS.2019.20MaRDI QIDQ5875653zbMATH OpenOpenAlexFDO

Authors Telikepalli Kavitha

Publication date 3 February 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/11582/pdf/LIPIcs-FSTTCS-2019-20.pdf/

zbMATH Keywords

dual certificatepopular matchingroommates instancestable matching

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• Popular matchings in the marriage and roommates problems
• Popular matching in roommates setting is \textsf{NP}-hard

Cited in

(4)

• Acyclic roommates
• Popular matchings with weighted voters
• Min-cost popular matchings
• Popular roommates in simply exponential time

This page was built for publication: Popular Roommates in Simply Exponential Time.

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