10 citations · 19 across the 11 of their papers we have counts for
8 papers · 1 filter
Discrete Incremental Voting on Expanders
Colin Cooper, Tomasz Radzik, Takeharu Shiraga
Pull voting is a random process in which vertices of a connected graph have initial opinions chosen from a set of distinct opinions, and at each step a random vertex alters its…
An analysis of load-balancing algorithms on edge-Markovian evolving graphs
Takeharu Shiraga, Shuji Kijima
Analysis of algorithms on time-varying networks (often called evolving graphs) is a modern challenge in theoretical computer science. The edge-Markovian is a relatively simple and…
Reversible Random Walks on Dynamic Graphs
Nobutaka Shimizu, Takeharu Shiraga
Recently, random walks on dynamic graphs have been studied because of their adaptivity to the time-varying structure of real-world networks. In general, there is a tremendous gap b…
Dispersion processes
Colin Cooper, Andrew McDowell, Tomasz Radzik +2
We study a synchronous dispersion process in which particles are initially placed at a distinguished origin vertex of a graph . At each time step, at each vertex occupie…
Fast plurality consensus in regular expanders
Colin Cooper, Tomasz Radzik, Nicolás Rivera +1
Pull voting is a classic method to reach consensus among vertices with differing opinions in a distributed network: each vertex at each step takes on the opinion of a random ne…
The Cover Time of Deterministic Random Walks for General Transition Probabilities
Takeharu Shiraga
The deterministic random walk is a deterministic process analogous to a random walk. While there are some results on the cover time of the rotor-router model, which is a determinis…
Total Variation Discrepancy of Deterministic Random Walks for Ergodic Markov Chains
Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima +1
Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper investigates deterministic random walks, which is a deterministic process analogous to a random walk.…
Deterministic Random Walks for Rapidly Mixing Chains
Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima +1
The rotor-router model is a deterministic process analogous to a simple random walk on a graph. This paper is concerned with a generalized model, functional-router model, which imi…