The problem of efficiently sampling from a set of(undirected) graphs with a given degree sequence has many applications. One approach to this problem uses a simple Markov chain, which we call the switch chain, to perform the sampling. The switch chain is known to be rapidly mixing for regular degree sequences. We prove that the switch chain is rapidly mixing for any degree sequence with minimum degree at least 1 and with maximum degree @math which satisfies @math , where @math is the sum of the degrees. The mixing time bound obtained is only an order of @math larger than that established in the regular case, where @math is the number of vertices.
@cite_0: Abstract An algorithm is presented which randomly selects a labelled graph with specified vertex degrees from a distribution which is arbitrarily close to uniform. The algorithm is based on simulation of a rapidly convergent stochastic process, and runs in polynomial time for a wide class of degree sequences, including all regular sequences and all n -vertex sequences with no degree exceeding √ n 2. The algorithm can be extended to cover the selection of a graph with given degree sequence which avoids a specified set of edges. One consequence of this extension is the existence of a polynomial-time algorithm for selecting an f -factor in a sufficiently dense graph. A companion algorithm for counting degree-constrained graphs is also presented; this algorithm has exactly the same range of validity as the one for selection.
@cite_10: This invention discloses apparatus and method for checking the calibration of a fluid turbine meter without interrupting the line service. A flow directions sensing means is inserted at the downstream side of the flowmeter so that the angle of flow the discharge from the meter may be checked from time to time without removing the meter from its flow line. Any change in this angle indicates a possible change in response of the meter.
Jerrum and Sinclair @cite_0 used a construction of Tutte's to reduce the problem of sampling from @math to the problem of sampling perfect matchings from an auxilliary graph. The resulting Markov chain algorithm is rapidly mixing if the degree sequence @math is : see @cite_10 . Stable sequences are those in which small local changes to the degree sequences do not greatly affect the size of @math . Many degree sequences which satisfy the conditions of Theorem are stable; however, not all stable sequences satisfy the conditions of Theorem . (For example, if @math and @math then @math is stable @cite_10 but then @math , which is not large enough for Theorem .)