1 citations · 1 across the 1 of their papers we have counts for
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…
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…
Incremental Optimization of Independent Sets under Reachability Constraints
Takehiro Ito, Haruka Mizuta, Naomi Nishimura +1
We introduce a new framework for reconfiguration problems, and apply it to independent sets as the first example. Suppose that we are given an independent set of a graph ,…
Reconfiguring spanning and induced subgraphs
Tesshu Hanaka, Takehiro Ito, Haruka Mizuta +5
Subgraph reconfiguration is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertice…