Effective data reduction for strongly stable matching in very sparse graphs

DOI10.1016/J.IPL.2024.106534MaRDI QIDQ6663523zbMATH OpenFDO

Authors Rosa Wolf, Klaus Heeger, André Nichterlein

Publication date 14 January 2025

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2024.106534

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27) Matching models (91B68)

Recommendations

• The strongly stable roommates problem
• Parameterized algorithms for stable matching with ties and incomplete lists
• The power of linear-time data reduction for maximum matching
• The Power of Linear-Time Data Reduction for Maximum Matching
• Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments

Cites work

• A new fixed point approach for stable networks and stable marriages
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Data Reduction for Maximum Matching on Real-World Graphs
• Hard variants of stable marriage.
• How hard is it to satisfy (almost) all roommates?
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 1962834 (Why is no real title available?)
• On the power of tree-depth for fully polynomial FPT algorithms
• On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
• Parameterized algorithms
• Parameterized algorithms for stable matching with ties and incomplete lists
• Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
• Strongly stable matchings in time \(O(nm)\) and extension to the hospitals-residents problem
• The power of linear-time data reduction for maximum matching
• The Stable Roommates Problem with Ties
• The strongly stable roommates problem

This page was built for publication: Effective data reduction for strongly stable matching in very sparse graphs

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