121 citations · 153 across the 25 of their papers we have counts for
32 papers
Rerouting Curves on Surfaces
Timo Brand, Stefan Felsner, Henry Förster +8
We study the problem of reconfiguring a crossing-free embedding of a graph on a surface, with edges represented as curves, into another crossing-free embedding of the same graph on…
Algorithmic Theory of Qubit Routing
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum progra…
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +4
We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open pro…
Reconfiguration of colorings in triangulations of the sphere
Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi +4
In 1973, Fisk proved that any -coloring of a -colorable triangulation of the -sphere can be obtained from any -coloring by a sequence of Kempe-changes. On the other han…
Rerouting Planar Curves and Disjoint Paths
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura +5
In this paper, we consider a transformation of disjoint paths in a graph. For a graph and a pair of disjoint paths and connecting the same set o…
On Reachable Assignments under Dichotomous Preferences
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +4
We consider the problem of determining whether a target item assignment can be reached from an initial item assignment by a sequence of pairwise exchanges of items between agents.…