Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove...
ALGORITHMS AND COMPUTATION, ISAAC 2014 8889 553-564 2014年 [査読有り]
We provide algorithms performing Depth-First Search (DFS) on a directed or undirected graph with n vertices and m edges using only O(n) bits. One algorithm uses O(n) bits and runs in O(mlog n) time. Another algorithm uses n+ o(n) bits and runs in ...
Katsuhisa Yamanaka   Erik D. Demaine   Takehiro Ito   Jun Kawahara   Masashi Kiyomi   Yoshio Okamoto   Toshiki Saitoh   Akira Suzuki   Kei Uchizawa   Takeaki Uno   
FUN WITH ALGORITHMS 8496 364-375 2014年 [査読有り]
Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove...
Takashi Horiyama   Masashi Kiyomi   Yoshio Okamoto   Ryuhei Uehara   Takeaki Uno   Yushi Uno   Yukiko Yamauchi   
FUN WITH ALGORITHMS 8496 230-239 2014年 [査読有り]
We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In...