The Graphs of Stably Matchable Pairs

October 19, 2020 · The Ethereal · 🏛 International Workshop on Graph-Theoretic Concepts in Computer Science

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors David Eppstein arXiv ID 2010.09230 Category cs.DM: Discrete Mathematics Cross-listed cs.DS Citations 1 Venue International Workshop on Graph-Theoretic Concepts in Computer Science Last Checked 5 months ago
Abstract
We study the graphs formed from instances of the stable matching problem by connecting pairs of elements with an edge when there exists a stable matching in which they are matched. Our results include the NP-completeness of recognizing these graphs, an exact recognition algorithm that is singly exponential in the number of edges of the given graph, and an algorithm whose time is linear in the number of vertices of the graph but exponential in a polynomial of its carving width. We also provide characterizations of graphs of stably matchable pairs that belong to certain classes of graphs, and of the lattices of stable matchings that can have graphs in these classes.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Discrete Mathematics