21 citations · 42 across the 14 of their papers we have counts for
16 papers
The Maker-Breaker Largest Connected Subgraph Game
Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney +2
Given a graph and , we introduce the following game played in . Each round, Alice colours an uncoloured vertex of red, and then Bob colours one blue (i…
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…
Problems, proofs, and disproofs on the inversion number
Guillaume Aubian, Frédéric Havet, Florian Hörsch +4
The {\it inversion} of a set of vertices in a digraph consists in reversing the direction of all arcs of . The {\it inversion number} of an oriented grap…