6 citations · 12 across the 11 of their papers we have counts for
3 papers · 1 filter
Fractional Matchings under Preferences: Stability and Optimality
Jiehua Chen, Sanjukta Roy, Manuel Sorge
We thoroughly study a generalized version of the classic Stable Marriage and Stable Roommates problems where agents may share partners. We consider two prominent stability concepts…
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
Thomas Bellitto, Shaohua Li, Karolina Okrasa +2
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is…
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwiński, Yann Disser +8
We present a data structure that in a dynamic graph of treedepth at most , which is modified over time by edge insertions and deletions, maintains an optimum-height elimination…