21 citations · 42 across the 14 of their papers we have counts for
3 papers · 1 filter
Complexity of Maker-Breaker Games on Edge Sets of Graphs
Eric Duchêne, Valentin Gledel, Fionn Mc Inerney +4
We study the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the -game. Maker wins if s…
On computing tree and path decompositions with metric constraints on the bags
Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse
We here investigate on the complexity of computing the \emph{tree-length} and the \emph{tree-breadth} of any graph , that are respectively the best possible upper-bounds on the…
Adding a referee to an interconnection network: What can(not) be computed in one round
Florent Becker, Martín Matamala, Nicolas Nisse +3
In this paper we ask which properties of a distributed network can be computed from a little amount of local information provided by its nodes. The distributed model we consider is…