8 citations · 15 across the 10 of their papers we have counts for
4 papers · 1 filter
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…
The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant
Jun Kawahara, Toshiki Saitoh, Ryo Yoshinaka
The problems of Permutation Routing via Matching and Token Swapping are reconfiguration problems on graphs. This paper is concerned with the complexity of those problems and a colo…
Computational Complexity of Competitive Diffusion on (Un)weighted Graphs
Takehiro Ito, Yota Otachi, Toshiki Saitoh +6
Consider an undirected graph modeling a social network, where the vertices represent users, and the edges do connections among them. In the competitive diffusion game, each of a nu…
Extending Partial Representations of Subclasses of Chordal Graphs
Pavel Klavik, Jan Kratochvil, Yota Otachi +1
Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial represen…