Nobutaka Shimizu, Takeharu Shiraga,
"Quasi-majority functional voting on expander graphs,"
Random Structures & Algorithms, to appear.
Keywords: distributed voting, consensus problem, expander graph, Markov chain

Nobutaka Shimizu, Takeharu Shiraga,
"Reversible random walks on dynamic graphs,"
Random Structures & Algorithms, 63(4), 1100-1136 (2023).
Keywords: dynamic graph, Markov chain, random walk

Nobutaka Shimizu, Takeharu Shiraga,
"Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models,"
Random Structures & Algorithms, 59(1), 96-140 (2021).
Keywords: consensus problem, distributed voting, random graph

Yuya Higashikawa, Keiko Imai, Takeharu Shiraga, Noriyoshi Sukegawa, Yusuke Yokosuka,
"Minimum point-overlap labelling,"
Optimization Methods and Software, 36(2-3), 316-325 (2021).
Keywords: map labelling, air-traffic control, approximation algorithms

Takeharu Shiraga,
"The cover time of deterministic random walks for general transition probabilities,"
Theoretical Computer Science, 815, 153-162 (2020).
Keywords: rotor-router model, stack walk, multiple random walks, mixing time, cover time

Colin Cooper, Andrew McDowell, Tomasz Radzik, Nicolas Rivera, Takeharu Shiraga,
"Dispersion processes,"
Random Structures & Algorithms, 53(4), 561-585 (2018).
Keywords: random processes on graphs, dispersion of particles, random walk

Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita,
"Deterministic random walks for rapidly mixing chains,"
SIAM Journal on Discrete Mathematics, 32(3), 2180-2193 (2018).
Keywords: rotor-router model, Markov chain Monte Carlo (MCMC), mixing time

Colin Cooper, Tomasz Radzik, Takeharu Shiraga,
"Discrete incremental voting,"
in Proceedings of the 27th International Conference on Principles of Distributed Systems (OPODIS 2023), 10:1-10:22.
Keywords: random distributed processes, pull voting

Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga,

"How many vertices does a random walk miss in a network with moderately increasing the number of vertices?,"
in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), 106-122.
Keywords: cover time, dynamic graph, evolving graph, temporal graph

Nobutaka Shimizu, Takeharu Shiraga,

"Quasi-majority functional voting on expander graphs,"

in Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 97:1-97:19.
Keywords: distributed voting, consensus problem, expander graph, Markov chain

Nobutaka Shimizu, Takeharu Shiraga,

"Phase transitions of Best-of-two and Best-of-three on stochastic block models,"
in Proceedings of the 33rd International Symposium on Distributed Computing (DISC 2019), 32:1-32:17.
Keywords: distributed voting, consensus problem, random graph

Colin Cooper, Tomasz Radzik, Nicolas Rivera, Takeharu Shiraga,

"Fast plurality consensus in regular expanders,"
in Proceedings of the 31st International Symposium on Distributed Computing (DISC 2017), 13:1-13:16.
Keywords: plurality consensus, regular expanders

Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita,
"Total variation discrepancy of deterministic random walks for ergodic Markov chains,"

in Proceedings of the meeting of Analytic Algorithmics and Combinatorics (ANALCO 2016), 138-148.
Keywords: rotor router model, Propp machine, load balancing, Markov chain Monte Carlo (MCMC), mixing time

Colin Cooper, Robert Elsasser, Tomasz Radzik, Nicolas Rivera, Takeharu Shiraga,

"Fast consensus for voting on general expander graphs,"

in Proceedings of the 29th International Symposium on Distributed Computing (DISC 2015), 248-262.
Keywords: random walk, transition matrix, random graph, edge weight, regular graph

Colin Cooper, Tomasz Radzik, Nicolas Rivera, Takeharu Shiraga,

"Coalescing walks on rotor-router systems,"

in Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2015), 444-458.
Keywords: regular graph, cyclic order, cover time, vertex pointer, coalescence time