29 citations · 53 across the 16 of their papers we have counts for
3 papers · 1 filter
Disjoint Stable Matchings in Linear Time
Aadityan Ganesh, Vishwa Prakash HV, Prajakta Nimbhorkar +1
We show that given a SM instance G as input we can find a largest collection of pairwise edge-disjoint stable matchings of G in time linear in the input size. This extends two clas…
Diverse Pairs of Matchings
Fedor V. Fomin, Petr A. Golovach, Lars Jaffke +2
We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph and an integer , ask whether has two (maximum/perfect) matchings w…
Structural Parameterizations of Clique Coloring
Lars Jaffke, Paloma T. Lima, Geevarghese Philip
A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the C…