16 citations · 22 across the 3 of their papers we have counts for
5 papers · 1 filter
Fixed-Parameter Algorithms for Graph Constraint Logic
Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito +3
Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures \PSPACE\xsp…
Complexity of Reconfiguration Problems for Constraint Satisfaction
Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou
Constraint satisfaction problem (CSP) is a well-studied combinatorial search problem, in which we are asked to find an assignment of values to given variables so as to satisfy all…
Shortest Reconfiguration of Matchings
Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito +1
Imagine that unlabelled tokens are placed on the edges of a graph, such that no two tokens are placed on incident edges. A token can jump to another edge if the edges having tokens…
Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou
Let be a graph such that each vertex has its list of available colors, and assume that each list is a subset of the common set consisting of colors. For two given list colo…
The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou
We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times mai…