CS Forum: Marthe Bonamy, LaBRI in Bordeaux "Combinatorial Reconfiguration"

Combinatorial Reconfiguration

Dr Marthe Bonamy
CNRS researcher at LaBRI in Bordeaux

Abstract:

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.