Strongly stable and maximum weakly stable noncrossing matchings

DOI10.1007/S00453-021-00832-9MaRDI QIDQ1979449zbMATH OpenOpenAlexFDO

Authors Koki Hamada, Shuichi Miyazaki, Kazuya Okamoto

Publication date 2 September 2021

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2001.08468

zbMATH Keywords

NP-completenesspolynomial-time algorithmsstable marriagenoncrossing matching

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Recommendations

• Strongly stable and maximum weakly stable noncrossing matchings
• Stable noncrossing matchings
• Stable marriage with ties and bounded length preference lists
• The Stable Roommates Problem with Ties
• Characterisation of strongly stable matchings

Cites work

• scientific article; zbMATH DE number 1617265 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 48303 (Why is no real title available?)
• scientific article; zbMATH DE number 3558960 (Why is no real title available?)
• scientific article; zbMATH DE number 1962834 (Why is no real title available?)
• A matching problem in the plane
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• College Admissions and the Stability of Marriage
• Computing maximum non-crossing matching in convex bipartite graphs
• Efficient labelling algorithms for the maximum noncrossing matching problem
• Jointly stable matchings
• Size versus stability in the marriage problem
• Some remarks on the stable matching problem
• Stable marriage and indifference
• Stable marriage with ties and bounded length preference lists
• Stable noncrossing matchings
• Strongly stable and maximum weakly stable noncrossing matchings
• Strongly stable matchings in time \(O(nm)\) and extension to the hospitals-residents problem
• The complexity of theorem-proving procedures
• ``Almost stable matchings in the roommates problem with bounded preference lists

Cited in

(4)

• Strongly stable and maximum weakly stable noncrossing matchings
• Algorithms and complexity of strongly stable non-crossing matchings
• Stable noncrossing matchings
• Zero forcing number, constrained matchings and strong structural controllability

This page was built for publication: Strongly stable and maximum weakly stable noncrossing matchings

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