3 citations · 6 across the 18 of their papers we have counts for
6 papers · 1 filter
Maximum Stable Matching with Matroids and Partial Orders
Gergely Csáji, Tamás Király, Yu Yokoi
The Stable Marriage problem (SM), solved by the famous deferred acceptance algorithm of Gale and Shapley (GS), has many natural generalizations. If we allow ties in preferences, th…
On the complexity of packing rainbow spanning trees
Kristóf Bérczi, Gergely Csáji, Tamás Király
One of the most important questions in matroid optimization is to find disjoint common bases of two matroids. The significance of the problem is well-illustrated by the long list o…
Manipulating the outcome of stable matching and roommates problems
Kristóf Bérczi, Gergely Csáji, Tamás Király
The stable marriage and stable roommates problems have been extensively studied due to their high applicability in various real-world scenarios. However, it might happen that no st…
Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity
Jiehua Chen, Gergely Csáji, Sanjukta Roy +1
We investigate verification and existence problems for prominent stability concepts in hedonic games with friends, enemies, and optionally with neutrals [8, 16]. We resolve several…
Strong core and Pareto-optimal solutions for the multiple partners matching problem under lexicographic preferences
Péter Biró, Gergely Csáji
In a multiple partners matching problem the agents can have multiple partners up to their capacities. In this paper we consider both the two-sided many-to-many stable matching prob…
Short proof of a theorem of Brylawski on the coefficients of the Tutte polynomial
Csongor Beke, Gergely Kál Csáji, Péter Csikvári +1
In this short note we show that a system with a ground set of size and (rank) function satisfying for ev…