4 papers
On the Distance Identifying Set meta-problem and applications to the complexity of identifying problems on graphs
Florian Barbero, Lucas Isenmann, Jocelyn Thiebaut
Numerous problems consisting in identifying vertices in graphs using distances are useful in domains such as network verification and graph isomorphism. Unifying them into a meta-p…
Quasiperiods of biinfinite Sturmian words
Florian Barbero, Guilhem Gamard, Anaël Grandjean
We study the notion of quasiperiodicity, in the sense of "coverability", for biinfinite words. All previous work about quasiperiodicity focused on right infinite words, but the pas…
Strong immersion is a well-quasi-ordering for semi-complete digraphs
Florian Barbero, Christophe Paul, Michal Pilipczuk
We prove that the strong immersion order is a well-quasi-ordering on the class of semi-complete digraphs, thereby strengthening a result of Chudnovsky and Seymour that this holds f…
Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
Florian Barbero, Christophe Paul, Michał Pilipczuk
A simple digraph is semi-complete if for any two of its vertices and , at least one of the arcs and is present. We study the complexity of computing two layo…