ランダムグラフの高速生成とランダムネスについて

概要

論文の詳細を見る
In this paper a high speed algorithm for generating random graphs is described together with the representations of some statistical characteristics of the randomness of generated graphs. At first, a concept of randomness of a set and its complements is proposed to speed up the computation of the ordinary algorithm for random graph generation. Then, algorithm is described in a form implementable on the computer based on this concept. The expected computational time of the proposed algorithm is the half of the time required theoretically by the ordinary method. This is certified by computer experiments and some results of these experiments are presented schematically. Then, the consistency of randomness of those generated graphs and ordinary ones is examined experimentally by checking the probability distribution of the appearance of each generated graphs in the set of the whole generated random graphs.
明治大学の論文