5 papers
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
Shuichi Hirahara, Nobutaka Shimizu
In this paper, we seek a natural problem and a natural distribution of instances such that any -time algorithm fails to solve most instances drawn from the distribution…
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga
Real networks are often dynamic. In response to it, analyses of algorithms on {\em dynamic networks} attract more and more attentions in network science and engineering. Random wal…
Quasi-majority Functional Voting on Expander Graphs
Nobutaka Shimizu, Takeharu Shiraga
Consider a distributed graph where each vertex holds one of two distinct opinions. In this paper, we are interested in synchronous voting processes where each vertex updates its op…
Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
Nobutaka Shimizu, Takeharu Shiraga
This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the \emph{Best-of-two} and the \emph{Best-of-…
Average Shortest Path Length of Graphs of Diameter 3
Nobutaka Shimizu, Ryuhei Mori
A network topology with low average shortest path length (ASPL) provides efficient data transmission while the number of nodes and the number of links incident to each node are oft…