8 citations · 36 across the 49 of their papers we have counts for
7 papers · 1 filter
Sequentially Swapping Tokens: Further on Graph Classes
Hironori Kiya, Yuto Okada, Hirotaka Ono +1
We study the following variant of the 15 puzzle. Given a graph and two token placements on the vertices, we want to find a walk of the minimum length (if any exists) such that the…
Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited
Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi +1
Given a graph and two vertex sets satisfying a certain feasibility condition, a reconfiguration problem asks whether we can reach one vertex set from the other by repeating prescri…
Independent set reconfiguration on directed graphs
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi +4
\textsc{Directed Token Sliding} asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a…
Finding shortest non-separating and non-disconnecting paths
Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi
For a connected graph and , a non-separating - path is a path between and such that the set of vertices of does not separate , tha…
Sorting Balls and Water: Equivalence and Computational Complexity
Takehiro Ito, Jun Kawahara, Shin-ichi Minato +7
Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled…
Extended MSO Model Checking via Small Vertex Integrity
Tatsuya Gima, Yota Otachi
We study the model checking problem of an extended with local and global cardinality constraints, called , introduced rece…
Frameworks to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi +4
Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world probl…