54 citations · 152 across the 16 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.DS2020
The Longest Run Subsequence Problem: Further Complexity Results
Riccardo Dondi, Florian Sikora
Longest Run Subsequence is a problem introduced recently in the context of the scaffolding phase of genome assembly (Schrinner et al., WABI 2020). The problem asks for a maximum le…
cs.DS2020
On the complexity of Broadcast Domination and Multipacking in digraphs
Florent Foucaud, Benjamin Gras, Anthony Perez +1
We study the complexity of the two dual covering and packing distance-based problems Broadcast Domination and Multipacking in digraphs. A dominating broadcast of a digraph is a…
cs.CC2020
Grundy Coloring & friends, Half-Graphs, Bicliques
Pierre Aboulker, Édouard Bonnet, Eun Jung Kim +1
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order , the smallest available color. The problem Grundy Coloring asks how many colors…