34 citations · 53 across the 16 of their papers we have counts for
20 papers
Resolving Envy by Adding Goods with Bounded Supply: A Type-Count Dichotomy and Two-Agent Hardness
Chuang-Chieh Lin, Guillaume Fertin, Po-An Chen +4
We study envy elimination by adding goods (EEAG) when the additional pool has bounded supply and no separate budget bound. We establish a sharp type-count dichotomy for binary addi…
Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms
Cyril Nicaud, Carine Pivoteau, Stéphane Vialette
We analyze the classical Morris-Pratt and Knuth-Morris-Pratt pattern matching algorithms through the lens of computer architecture, investigating the impact of incorporating a simp…
Generalizing Roberts' characterization of unit interval graphs
Virginia Ardévol Martínez, Romeo Rizzi, Abdallah Saffidine +2
For any natural number , a graph is a (disjoint) -interval graph if it is the intersection graph of (disjoint) -intervals, the union of (disjoint) intervals on the…
Quasi-kernels in split graphs
Hélène Langlois, Frédéric Meunier, Romeo Rizzi +2
In a digraph, a quasi-kernel is a subset of vertices that is independent and such that the shortest path from every vertex to this subset is of length at most two. The ``small quas…
Recognizing unit multiple intervals is hard
Virginia Ardévol Martínez, Romeo Rizzi, Florian Sikora +1
Multiple interval graphs are a well-known generalization of interval graphs introduced in the 1970s to deal with situations arising naturally in scheduling and allocation. A -in…
Algorithmic aspects of quasi-kernels
Hélène Langlois, Frédéric Meunier, Romeo Rizzi +1
In a digraph, a quasi-kernel is a subset of vertices that is independent and such that every vertex can reach some vertex in that set via a directed path of length at most two. Whe…