21 citations · 42 across the 14 of their papers we have counts for
4 papers · 1 filter
Weakly synchronous systems with three machines are Turing powerful
Cinzia Di Giusto, Davide Ferré, Etienne Lozes +1
Communicating finite-state machines (CFMs) are a Turing powerful model of asynchronous message-passing distributed systems. In weakly synchronous systems, processes communicate thr…
Redicolouring digraphs: directed treewidth and cycle-degeneracy
Nicolas Nisse, Lucas Picasarri-Arrieta, Ignasi Sau
Given a digraph on vertices and a vertex , the cycle-degree of is the minimum size of a set intersecting every directed…
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…
Digraph redicolouring
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse +2
Given two -dicolourings of a digraph , we prove that it is PSPACE-complete to decide whether we can transform one into the other by recolouring one vertex at each step while…