21 citations · 64 across the 25 of their papers we have counts for
4 papers · 1 filter
Algorithmic aspects of quasi-kernels
Hélène Langlois, Frédéric Meunier, Romeo Rizzi +1
In a digraph, a quasi-kernel is a subset of vertices that is independent and such that every vertex can reach some vertex in that set via a directed path of length at most two. Whe…
Perfect graphs with polynomially computable kernels
Adèle Pass-Lanneau, Ayumi Igarashi, Frédéric Meunier
In a directed graph, a kernel is a subset of vertices that is both stable and absorbing. Not all digraphs have a kernel, but a theorem due to Boros and Gurvich guarantees the exist…
Colorful linear programming, Nash equilibrium, and pivots
Frédéric Meunier, Pauline Sarrabezolles
The colorful Carathéodory theorem, proved by Bárány in 1982, states that given d+1 sets of points S_1,...,S_{d+1} in R^d, with each S_i containing 0 in its convex hull, there exist…
Directed paths on a tree: coloring, multicut and kernel
Olivier Durand de Gévigney, Frédéric Meunier, Christian Popa +2
In the present paper, we study algorithmic questions for the arc-intersection graph of directed paths on a tree. Such graphs are known to be perfect (proved by Monma and Wei in 198…