CS Forum: Marthe Bonamy, LaBRI in Bordeaux "Combinatorial Reconfiguration"
Dr Marthe Bonamy
CNRS researcher at LaBRI in Bordeaux
Given a problem and a first solution to it, we can reconfigure that solution, i.e. successively apply elementary operations -- while staying within the solution space. Such a need appears naturally in dynamic settings, where a given solution is already in place and must be modified, yet no service disruption can be afforded.
Several major questions are considered: which elementary operations guarantee that we can thus reach any other solution? For fixed operations, what is the complexity of deciding whether we can reach a given solution? What about the number of steps necessary for that? By iteratively applying random elementary operations, how long before we have a "random" solution?
In this talk, we will discuss various positive and negative results around classical graph problems.
CS forum is a seminar series arranged at the CS department. The talks are intended for presentations of postdoctoral level researchers and professors, both for visiting and CS-department-based researchers.