Popular roommates in simply exponential time

DOI10.1007/S00453-024-01287-4MaRDI QIDQ7027525zbMATH OpenFDO

Authors Telikepalli Kavitha

Publication date 14 February 2025

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-024-01287-4

zbMATH Keywords

dual certificatesnon-bipartite graphspopular matchingsstable matchings

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Matching models (91B68)

Cites work

• A New Approach to Stable Matching Problems
• A simply exponential upper bound on the maximum number of stable matchings
• A Size-Popularity Tradeoff in the Stable Marriage Problem
• A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the Technion
• An efficient algorithm for the “stable roommates” problem
• At most 3.55ⁿ stable matchings
• College Admissions and the Stability of Marriage
• Concerning the maximum number of stable matchings in the stable marriage problem
• Efficient algorithms for generalized stable marriage and roommates problems
• Exact exponential algorithms.
• Faster algorithms for stable allocation problems
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 3637616 (Why is no real title available?)
• scientific article; zbMATH DE number 7657254 (Why is no real title available?)
• Integer Programming: Methods, Uses, Computations
• Maximum matching and a polyhedron with 0,1-vertices
• Near-popular matchings in the roommates problem
• On the existence of stable roommate matchings
• Popular edges and dominant matchings
• Popular Half-Integral Matchings.
• Popular matching in roommates setting is NP-hard
• Popular Matchings
• Popular matchings and limits to tractability
• Popular matchings in complete graphs
• Popular matchings in the marriage and roommates problems
• Popular matchings in the stable marriage problem
• Popular matchings with two-sided preferences and one-sided ties
• Popular mixed matchings
• Popular Roommates in Simply Exponential Time.
• Popularity, Mixed Matchings, and Self-Duality
• Sex-equal stable matchings: complexity and exact algorithms
• The geometry of fractional stable matchings and its applications
• The popular assignment problem: when cardinality is more important than popularity
• Two problems in max-size popular matchings

Cited in

(1)

• Testing popularity in linear time via maximum matching

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 Q7027525)