Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Complexity Thresholds for the Constrained Colored Token Swapping Problem
Davide Bilò, Stefano Leucci, Andrea Martinelli
Consider the following puzzle: a farmland consists of several fields, each occupied by either a farmer, a fox, a chicken, or a caterpillar. Creatures in neighboring fields can swap…
cs.CC2024
On the approximability of graph visibility problems
Davide Bilò, Alessia Di Fonso, Gabriele Di Stefano +1
Visibility problems have been investigated for a long time under different assumptions as they pose challenging combinatorial problems and are connected to robot navigation problem…
cs.CC2024
On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
Davide Bilò, Giordano Colli, Luca Forlizzi +1
Given an undirected connected graph on vertices, the minimum Monitoring Edge-Geodetic Set (MEG-set) problem asks to find a subset of minim…