9 citations · 11 across the 17 of their papers we have counts for
12 papers · 1 filter
On the parameterized complexity of the Maker-Breaker domination game
Guillaume Bagan, Mathieu Hilaire, Nacim Oijid +1
Since its introduction as a Maker-Breaker positional game by Duchêne et al. in 2020, the Maker-Breaker domination game has become one of the most studied positional games on vertic…
Exact number of flips required to sort a burnt stack of pancakes
Gerold Jäger, Nacim Oijid
In this work, we consider the burnt pancake problem, which is a well-studied problem going back to a work of Gates and Papadimitriou from 1979.The problem is to sort a stack of~…
Graph Irregularity via Edge Deletions
Julien Bensmail, Noémie Catherinot, Foivos Fioravantes +2
We pursue the study of edge-irregulators of graphs, which were recently introduced in [Fioravantes et al. Parametrised Distance to Local Irregularity. IPEC, 2024]. That is, we are…
Computing the degreewidth of a digraph is hard
Pierre Aboulker, Nacim Oijid, Robin Petit +2
Given a digraph, an ordering of its vertices defines a backedge graph, namely the undirected graph whose edges correspond to the arcs pointing backwards with respect to the order.…
On the complexity of Client-Waiter and Waiter-Client games
Valentin Gledel, Nacim Oijid, Sébastien Tavenas +1
Positional games were introduced by Hales and Jewett in 1963, and their study became more popular after Erdos and Selfridge's first result on their connection to Ramsey theory and…
Poset Positional Games
Guillaume Bagan, Eric Duchêne, Florian Galliot +5
We propose a generalization of positional games, supplementing them with a restriction on the order in which the elements of the board are allowed to be claimed. We introduce poset…
Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles
Kyle Burke, Antoine Dailly, Nacim Oijid
Arc-Kayles is a game where two players alternate removing two adjacent vertices until no move is left, the winner being the player who played the last move. Introduced in 1978, its…
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…
The Maker-Maker domination game in forests
Eric Duchêne, Arthur Dumas, Nacim Oijid +2
We study the Maker-Maker version of the domination game introduced in 2018 by Duchêne et al. Given a graph, two players alternately claim vertices. The first player to claim a domi…
Incidence, a Scoring Positional Game on Graphs
Guillaume Bagan, Quentin Deschamps, Eric Duchêne +5
Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where…
Avoidance games are PSPACE-Complete
Valentin Gledel, Nacim Oijid
Avoidance games are games in which two players claim vertices of a hypergraph and try to avoid some structures. These games are studied since the introduction of the game of SIM in…
Bipartite instances of INFLUENCE
Eric Duchêne, Nacim Oijid, Aline Parreau
The game INFLUENCE is a scoring combinatorial game that has been introduced in 2020 by Duchene et al. It is a good representative of Milnor's universe of scoring games, i.e. games…