Showing cs.CCShow all
2 papers · 1 filter
cs.CC2023
Minimum Separator Reconfiguration
Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud +4
We study the problem of reconfiguring one minimum --separator into another minimum --separator in some -vertex graph containing two non-adjacent vertices…
cs.CC2021
Parameterized complexity of untangling knots
Clément Legrand-Duchesne, Ashutosh Rai, Martin Tancer
Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized…