10 papers
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~…
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…
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.…
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…
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…