4 citations · 9 across the 9 of their papers we have counts for
5 papers · 1 filter
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 ,…
The Complexity of (List) Edge-Coloring Reconfiguration Problem
Hiroki Osawa, Akira Suzuki, Takehiro Ito +1
Let be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of colors. Suppose that we are given…
The complexity of dominating set reconfiguration
Arash Haddadan, Takehiro Ito, Amer E. Mouawad +4
Suppose that we are given two dominating sets and of a graph whose cardinalities are at most a given threshold . Then, we are asked whether there exists a sequen…
Reconfiguration of Dominating Sets
Akira Suzuki, Amer E. Mouawad, Naomi Nishimura
We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph is a set of vertices such that each vertex is either in or has a n…