Testing popularity in linear time via maximum matching

DOI10.1016/J.DAM.2025.01.014MaRDI QIDQ7021389zbMATH OpenFDO

Authors Erika R. Bérczi-Kovács, Kata Kosztolányi

Publication date 28 February 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.01.014

zbMATH Keywords

linear-time algorithmpopular matchingpopularity testing

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Linear programming (90C05)

Cites work

• A linear-time algorithm for a special case of disjoint set union
• A Size-Popularity Tradeoff in the Stable Marriage Problem
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• An efficient algorithm for the “stable roommates” problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Faster scaling algorithms for general graph matching problems
• On the existence of stable roommate matchings
• Popular Half-Integral Matchings.
• Popular matching in roommates setting is NP-hard
• Popular matchings and limits to tractability
• Popular matchings in the marriage and roommates problems
• Popular matchings in the stable marriage problem
• Popular Mixed Matchings
• Popular roommates in simply exponential time

This page was built for publication: Testing popularity in linear time via maximum matching

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