AbstractWe 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 (di)i=1n with maximum degree dmax =O(m1/4−τ), our algorithm generates almost uniform random graphs with that degree sequence in time O(mdmax ) where $m=\frac{1}{2}\sum_{i}d_{i}$ is the number of edges in the graph and τ is any positive constant. The fastest known algorithm for uniform generation of these graphs (McKay and Wormald in J. Algorithms 11(1):52–67, 1990) has a running time of O(m2dmax 2). Our method also gives an independent proof of McKay’s estimate (McKay in Ars Combinatoria A 19:15–25, 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 dmax =O(m1/4−τ).Moreover, we show that for d=O(n1/2−τ), our algorithm can generate an asymptotically uniform d-regular graph. Our results improve the previous bound of d=O(n1/3−τ) due to Kim and Vu (Adv. Math. 188:444–469, 2004) for regular graphs.
ABSTRACT
PUBLICATION RECORD
- Publication year
2007
- Venue
Algorithmica
- Publication date
2007-02-22
- Fields of study
Mathematics, Computer Science
- Identifiers
- External record
- Source metadata
Semantic Scholar
CITATION MAP
EXTRACTION MAP
CLAIMS
- No claims are published for this paper.
CONCEPTS
- No concepts are published for this paper.
REFERENCES
Showing 1-55 of 55 references · Page 1 of 1