3 papers
cs.CC2025
The tape reconfiguration problem and its consequences for dominating set reconfiguration
Nicolas Bousquet, Quentin Deschamps, Arnaud Mary +2
A dominating set of a graph is a set of vertices whose closed neighborhood is , i.e., . We view a dominating set as a collection of tokens plac…
cs.CC2024
Complexity of the Swap Median and Swap Closest Problems
Luís Cunha, Thiago Lopes, Arnaud Mary
Genome rearrangement distances provide a combinatorial framework for comparing genomes represented as permutations. Although the swap distance between two permutations is polynomia…
math.CO2024
Enumeration of minimal transversals of hypergraphs of bounded VC-dimension
Arnaud Mary
We consider the problem of enumerating all minimal transversals (also called minimal hitting sets) of a hypergraph . An equivalent formulation of this problem known as…