8 citations · 36 across the 49 of their papers we have counts for
5 papers · 1 filter
Reconfiguration of Cliques in a Graph
Takehiro Ito, Hirotaka Ono, Yota Otachi
We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-st…
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…
Linear-Time Algorithm for Sliding Tokens on Trees
Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein +6
Suppose that we are given two independent sets and of a graph such that , and imagine that a token is placed on each vertex in . Then, the sliding tok…
A lower bound on opaque sets
Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi +1
It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This…
Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
Yota Otachi, Pascal Schweitzer
We study the parameterized complexity of the graph isomorphism problem when parameterized by width parameters related to tree decompositions. We apply the following technique to ob…