29 citations · 63 across the 22 of their papers we have counts for
6 papers · 1 filter
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…
b-Coloring Parameterized by Clique-Width
Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov
We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph clas…
Well-partitioned chordal graphs: obstruction set and disjoint paths
Jungho Ahn, Lars Jaffke, O-joung Kwon +1
We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the ve…
Hedonic Seat Arrangement Problems
Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke +3
In this paper, we study a variant of hedonic games, called \textsc{Seat Arrangement}. The model is defined by a bijection from agents with preferences for each other to vertices in…
Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach
Lars Jaffke, Mateus de Oliveira Oliveira, Hans Raj Tiwary
It can be shown that each permutation group can be embedded, in a well defined sense, in a connected graph with vertices. Some groups, however, requi…