5 papers
Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint
Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi +4
We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The e…
Linear transformations between dominating sets in the TAR-model
Nicolas Bousquet, Alice Joffard, Paul Ouvrard
Given a graph and an integer , a token addition and removal ({\sf TAR} for short) reconfiguration sequence between two dominating sets and of size at…
Reconfiguration of Spanning Trees with Many or Few Leaves
Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi +4
Let be a graph and be two spanning trees of . We say that can be transformed into via an edge flip if there exist two edges and in $T_2…
Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
Alexandre Blanché, Haruka Mizuta, Paul Ouvrard +1
Given a dominating set, how much smaller a dominating set can we find through elementary operations? Here, we proceed by iterative vertex addition and removal while maintaining the…
Distributed Recoloring
Marthe Bonamy, Paul Ouvrard, Mikaël Rabie +2
Given two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the gra…