2 papers
cs.GT2024
Popular Maximum-Utility Matchings with Matroid Constraints
Gergely Csáji, Tamás Király, Kenjiro Takazawa +1
We investigate weighted settings of popular matching problems with matroid constraints. The concept of popularity was originally defined for matchings in bipartite graphs, where ve…
cs.DS2024
Finding Spanning Trees with Perfect Matchings
Kristóf Bérczi, Tamás Király, Yusuke Kobayashi +2
We investigate the tractability of a simple fusion of two fundamental structures on graphs, a spanning tree and a perfect matching. Specifically, we consider the following problem:…