9 citations · 11 across the 17 of their papers we have counts for
7 papers · 1 filter
A two-player version of the assignment problem
Florian Galliot, Nacim Oijid, Jonas Sénizergues
We introduce the competitive assignment problem, a two-player version of the well-known assignment problem. Given a set of tasks and a set of agents with different efficiencies for…
On the Complexity of Vertex-Splitting Into an Interval Graph
Faisal N. Abu-Khzam, Dipayan Chakraborty, Lucas Isenmann +1
Vertex splitting is a graph modification operation in which a vertex is replaced by multiple vertices such that the union of their neighborhoods equals the neighborhood of the orig…
An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
Clara Marcille, Nacim Oijid
A monitoring edge-geodetic set (or meg-set for short) of a graph is a set of vertices such that if any edge is removed, then the distance between some two vertices of incre…
Token positional games
Guillaume Bagan, Quentin Deschamps, Florian Galliot +2
The classical Maker-Breaker positional game is played on a board which is a hypergraph , with two players, Maker and Breaker, alternately claiming vertices of $\mathca…
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…
On the complexity of the Maker-Breaker happy vertex game
Mathieu Hilaire, Perig Montfort, Nacim Oijid
Given a c-colored graph G, a vertex of G is happy if it has the same color as all its neighbors. The notion of happy vertices was introduced by Zhang and Li to compute the homophil…
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~…