5 citations · 12 across the 8 of their papers we have counts for
9 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…
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…
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest…
The Perfect Matching Reconfiguration Problem
Marthe Bonamy, Nicolas Bousquet, Marc Heinrich +5
We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a fl…
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…