||Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga, How many vertices does a random walk miss in a network with moderately increasing the number of vertices?, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), 10.1137/1.9781611976465.8, 106-122, 2021.01, Real networks are often dynamic. In response to it, analyses of algorithms on dynamic networks attract more and more attention in network science and engineering. Random walks on dynamic graphs also have been investigated actively in more than a decade, where in most cases the edge set changes but the vertex set is static. The vertex sets are also dynamic in many real networks. Motivated by a new technology of the analysis of random walks on dynamic graphs, this paper introduces a simple model of graphs with an increasing number of vertices and presents an analysis of random walks associated with the cover time on such graphs. In particular, we reveal that a random walk asymptotically covers the vertices all but a constant number if the vertex set grows moderately..
||Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, Deterministic random walks for rapidly mixing chains, SIAM Journal on Discrete Mathematics, 10.1137/16M1087667, 32, 3, 2180-2193, 2018.08, The rotor-router model is a deterministic process analogous to a simple random walk on a graph, and the discrepancy of token configurations between the rotor-router model and its corresponding random walk has been investigated in some contexts. Motivated by general Markov chains beyond simple random walks, this paper investigates a generalized model which imitates a Markov chain (of multiple tokens) possibly containing irrational transition probabilities. We are concerned with the vertexwise discrepancy of the numbers of tokens between the generalized model and its corresponding Markov chain, and present an upper bound of the discrepancy in terms of the mixing time of the Markov chain..
||Yukiko Yamauchi, Taichi Uehara, Shuji Kijima, Masafumi Yamashita, Plane formation by synchronous mobile robots in the three-dimensional Euclidean space, Journal of the ACM, 10.1145/3060272, 64, 3, 2017.06, Creating a swarm of mobile computing entities, frequently called robots, agents, or sensor nodes, with self-organization ability is a contemporary challenge in distributed computing. Motivated by this, we investigate the plane formation problem that requires a swarm of robots moving in the three-dimensional Euclidean space to land on a common plane. The robots are fully synchronous and endowed with visual perception. But they do not have identifiers, nor access to the global coordinate system, nor any means of explicit communication with each other. Though there are plenty of results on the agreement problem for robots in the two-dimensional plane, for example, the point formation problem, the pattern formation problem, and so on, this is the first result for robots in the three-dimensional space. This article presents a necessary and sufficient condition for fully synchronous robots to solve the plane formation problem that does not depend on obliviousness, i.e., the availability of local memory at robots. An implication of the result is somewhat counter-intuitive: The robots cannot form a plane from most of the semi-regular polyhedra, while they can form a plane from every regular polyhedron (except a regular icosahedron), whose symmetry is usually considered to be higher than any semi-regular polyhedron..
||Shuji Kijima, Kentaro Koga, Kazuhisa Makino, Deterministic random walks on finite graphs, Random Structures & Algorithms, 10.1002/rsa.20533, 46, 4, 739-761, 2015.07.
||Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno, Subgraph isomorphism in graph classes, Discrete Mathematics, 10.1016/j.disc.2012.07.010, 312, 21, 3164--3173, 2012.11.
||Shuji Kijima and Shin-ichi Tanigawa, Sparsity and connectivity of medial graphs: concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits, Discrete Mathematics, 10.1016/j.disc.2012.04.013, 312, 16, 2466--2472, 2012.08.
||Shuji Kijima and Toshio Nemoto, On randomized approximation for finding a level ideal of a poset and the generalized median stable matchings, Mathematics of Operations Research, 10.1287/moor.1110.0526, 2012.05.
||Shota Yasutake, Kohei Hatano, Shuji Kijima, Eiji Takimoto, Masayuki Takeda, Online linear optimization over permutations, Lecture Notes in Computer Science, 10.1007/978-3-642-25591-5_55, 7074, 534--543, 2011.12.
||Masatora Ogata, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita, A randomized algorithm for finding frequent elements in streams using O(loglog N) space, Lecture Notes in Computer Science, 10.1007/978-3-642-25591-5_53, 7074, 514--523, 2011.12.
||Shuji Kijima and Tomomi Matsui, Polynomial time perfect sampling algorithm for two-rowed contingency tables, Random Structures and Algorithms, 10.1002/rsa.v29:2, 29, 2, 243--256, 2006.09.