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−τ ), our algorithm generates almost uniform random graphs with that degree sequence in time O(md max ) where 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(m 2 d max 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.
展开▼
机译：我们提出了一种近乎线性的时间算法，用于计算和随机生成具有一定范围内给定度数序列的简单图。对于度数序列（d i ） i = 1 n ，最大度数d max = O（m 1 / 4−τ ），我们的算法会在时间O（md max ）中以该度数序列生成几乎均匀的随机图，其中θ是图中的边数，而τ是任意的正常数。均匀生成这些图的最快已知算法（McKay和Wormald in J.算法11（1）：52-67，1990年）的运行时间为O（m 2 d max 2 ）。我们的方法还为此类图的数量提供了麦凯估计的独立证明（McKay in Ars Combinatoria A 19：15–25，1985年）。
展开▼
