| Report ID: | 06-06-4123-22 |
| Initial Submission Date: | 2006-06-04 |
| Title: | Fast Generation of Random Graphs via Sequential Importance Sampling |
| Summary: | In this article we use sequential importance sampling to develop an efficient algorithm for generating simple random graphs with a given degree sequence. If the degree sequence is such that dmax = o(m^(1/4−Epsilon)), our algorithm generates an asymptotically uniform random graph with that degree sequence in almost linear time. Here dmax is maximum degree and m is the number of edges in the graphs. Our method also gives an independent proof of McKay and Wormald’s estimate [28] for number of graphs. |
| Authors: | Bayati, Mohsen; Saberi, Amin |
| Contact email: | bayati@stanford.edu |
| | Number of views : 875 Number of downloads : 428 |
