Computer Science – Computational Complexity
Scientific paper
2007-02-22
Algorithmica (2010) 58: 860-910
Computer Science
Computational Complexity
39 pages
Scientific paper
10.1007/s00453-009-9340-1
We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence $(d_i)_{i=1}^n$ with maximum degree $d_{\max}=O(m^{1/4-\tau})$, our algorithm generates almost uniform random graphs with that degree sequence in time $O(m\,d_{\max})$ where $m=\f{1}{2}\sum_id_i$ is the number of edges in the graph and $\tau$ is any positive constant. The fastest known algorithm for uniform generation of these graphs McKay Wormald (1990) has a running time of $O(m^2d_{\max}^2)$. Our method also gives an independent proof of McKay's estimate McKay (1985) for the number of such graphs. We also use sequential importance sampling to derive fully Polynomial-time Randomized Approximation Schemes (FPRAS) for counting and uniformly generating random graphs for the same range of $d_{\max}=O(m^{1/4-\tau})$. Moreover, we show that for $d = O(n^{1/2-\tau})$, our algorithm can generate an asymptotically uniform $d$-regular graph. Our results improve the previous bound of $d = O(n^{1/3-\tau})$ due to Kim and Vu (2004) for regular graphs.
Bayati Mohsen
Kim Jeong Han
Saberi Amin
No associations
LandOfFree
A Sequential Algorithm for Generating Random Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Sequential Algorithm for Generating Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Sequential Algorithm for Generating Random Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-101977