Effective data reduction for strongly stable matching in very sparse graphs

DOI10.1016/j.ipl.2024.106534MaRDI QIDQ6663523

André Nichterlein, Klaus Heeger, Rosa Wolf

Publication date: 14 January 2025

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

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• A new fixed point approach for stable networks and stable marriages
• Hard variants of stable marriage.
• 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
• The power of linear-time data reduction for maximum matching
• Strongly stable matchings in time O ( nm ) and extension to the hospitals-residents problem
• The Stable Roommates Problem with Ties
• On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
• The Strongly Stable Roommates Problem
• How hard is it to satisfy (almost) all roommates
• On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization)
• Data Reduction for Maximum Matching on Real-World Graphs
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Algorithmics of Matching Under Preferences
• Parameterized Algorithms

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