Name
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. |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1016/0304-3975(90)90164-D | Theor. Comput. Sci. |
Keywords | DocType | Volume |
regular graph,uniform generation | Journal | 73 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 48 |
PageRank | References | Authors |
8.49 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| JerrumMark | 1 | 199 | 33.55 |
| A. Sinclair | 2 | 48 | 8.49 |